Решение: Каменная куча и стратегия
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или четыре камня либо увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда количество камней в куче становится не менее 58. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой находится 58 или больше камней. В начальный момент в куче было $S$ камней, $1 \leq S \leq 57$. Укажите минимальное значение $S$, при котором Петя не может выиграть за один ход, но после любого хода Пети Ваня может выиграть своим первым ходом.
Решение по шагам
5 шаговПетя не должен иметь возможности выиграть за один ход. Для этого ни один из результатов его ходов не должен быть не менее 58. В частности, $2S < 58$, поэтому $S \leq 28$.
После любого хода Пети Ваня должен иметь возможность выиграть одним ходом. Если после хода Пети в куче $x$ камней, то Ваня выигрывает при $x \geq 29$ удвоением, при $x \geq 54$ добавлением 4 или при $x \geq 57$ добавлением 1.
Проверим минимально необходимое условие для самого малого хода Пети: $S+1 \geq 29$. Отсюда $S \geq 28$.
При $S=28$ после ходов Пети получится соответственно $29$, $32$ или $56$ камней. Ваня в каждом случае выигрывает удвоением: $29 \cdot 2=58$, $32 \cdot 2=64$, $56 \cdot 2=112$.
При этом Петя сам не может выиграть первым ходом, поскольку $28+4=32<58$ и $28\cdot2=56<58$.
Где здесь ошибаются
Проверяют только возможность удвоения, не учитывая ходы с добавлением 1 и 4 камней.
Считают выигрышной позицию, из которой можно достичь 58 только за несколько ходов.
Забывают, что при $S=28$ Петя сам ещё не может получить 58 камней одним ходом.