Решение: Выигрышная стратегия в игре
Документ к заданиюИнструкция к заданиям
Прочитайте текст и выполните задания.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или четыре камня либо увеличить количество камней в куче в три раза. Игра завершается в тот момент, когда количество камней в куче становится не менее 58. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, состоящую из 58 или более камней. В начальный момент в куче было $S$ камней, где $1 \leq S \leq 57$. Игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Укажите такое значение $S$, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Решение по шагам
4 шагаПетя не должен получить не менее 58 камней после своего первого хода. Поэтому проверяем все возможные ходы:
$$S+1<58,\quad S+4<58,\quad 3S<58$$Наиболее сильное ограничение даёт умножение количества камней на три: $3S<58$, откуда $S\leq 19$.
Проверим значение $S=19$. После ходов Пети количество камней может стать равным $20$, $23$ или $57$.
Из позиции $20$ Ваня умножает количество камней на три и получает $60$. Из позиции $23$ он получает $69$ тем же ходом, а из позиции $57$ добавляет один камень и получает $58$.
Где здесь ошибаются
Проверяют только ход с прибавлением камней и не учитывают умножение на три.
Забывают, что игра заканчивается сразу после получения 58 или более камней.
Не проверяют ответ после каждого возможного первого хода Пети.