Решение: Стратегия игры с камнями
Документ к заданиюИнструкция к заданиям по информатике
Прочитайте текст и выполните задания.
Два игрока, Петя и Ваня, играют в игру с кучей камней. Первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Игра завершается, когда количество камней становится не менее 129. Побеждает игрок, сделавший последний ход. В начальный момент в куче было $S$ камней, $1 \leq S \leq 128$. Укажите такое значение $S$, при котором Петя не может выиграть за один ход, но после любого хода Пети Ваня может выиграть своим первым ходом.
Решение по шагам
5 шаговЧтобы Петя не выиграл первым ходом, оба его возможных результата должны быть меньше 129:
$$S+1<129,\quad 2S<129$$Из второго неравенства следует $S\leq 64$. Значение $S=64$ является наибольшим возможным кандидатом.
Проверим оба хода Пети при $S=64$. Если Петя добавит один камень, в куче станет 65 камней, и Ваня удвоит количество: $65\cdot 2=130$.
Если Петя удвоит количество камней, в куче станет 128 камней, и Ваня добавит один камень: $128+1=129$.
В обоих случаях Ваня выигрывает своим первым ходом, поэтому подходящее значение — $S=64$.
Где здесь ошибаются
Проверяют только один из двух возможных ходов Пети.
Считают выигрышной позицию только при достижении ровно 129, хотя игра завершается и при большем количестве камней.
Выбирают $S=65$, не учитывая, что Петя может сразу удвоить количество камней.