Решение: Выигрышная стратегия в игре
Документ к заданиюИнструкция к заданиям по информатике
Прочитайте текст и выполните задания.
Два игрока, Петя и Ваня, играют в игру с кучей камней. Первый ход делает Петя. За один ход игрок может добавить в кучу 1 или 4 камня либо увеличить количество камней в куче в 2 раза. Игра завершается, когда количество камней становится не менее 35; победитель — игрок, сделавший последний ход. В начальный момент в куче было $S$ камней, где $1 \leq S \leq 34$. Укажите такое значение $S$, при котором Петя не может выиграть за один ход, но после любого хода Пети Ваня может выиграть своим первым ходом.
Решение по шагам
5 шаговЧтобы Петя не выиграл первым ходом, после каждого возможного хода количество камней должно быть меньше 35:
$$S+1<35,\quad S+4<35,\quad 2S<35$$Из условия $2S<35$ следует $S\leq 17$. Именно это ограничение является наиболее сильным.
Проверим $S=17$. После ходов Пети получаются кучи из $18$, $21$ или $34$ камней.
Из положения с 18 или 21 камнем Ваня удваивает количество камней: $18\cdot 2=36$, $21\cdot 2=42$. Из положения с 34 камнями Ваня добавляет один камень: $34+1=35$.
Следовательно, при любом ходе Пети Ваня выигрывает своим первым ходом.
Где здесь ошибаются
Проверяют только возможность удвоения и не учитывают ходы с добавлением 1 или 4 камней.
Забывают, что Ваня должен иметь выигрышный ответ после каждого возможного хода Пети.