Решение: Стратегия игры с камнями
Документ к заданиюИнструкция к заданиям по информатике
Прочитайте текст и выполните задания.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или четыре камня либо увеличить количество камней в куче в три раза. Игра завершается в тот момент, когда количество камней в куче становится не менее 85. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, состоящую из 85 или более камней. В начальный момент в куче было $S$ камней, $1 \leq S \leq 84$. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Укажите такое значение $S$, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Решение по шагам
5 шаговЧтобы Петя не выиграл первым ходом, все возможные результаты его ходов должны быть меньше 85:
$$S+1<85,\quad S+4<85,\quad 3S<85$$Наиболее ограничивающим является условие $3S<85$, поэтому $S\leq 28$.
Проверим значение $S=28$. После ходов Пети возможны позиции $29$, $32$ и $84$.
Из позиции $29$ Ваня умножает количество камней на 3 и получает $87$. Из позиции $32$ он получает $96$, умножив количество камней на 3. Из позиции $84$ Ваня добавляет один камень и получает $85$.
Следовательно, при любом первом ходе Пети Ваня выигрывает своим первым ходом, а Петя не может выиграть сразу.
Где здесь ошибаются
Проверяют только один возможный ход Пети, а не все три.
Забывают, что игра заканчивается при количестве камней не менее 85.
Выбирают значение, при котором Петя сам может получить 85 или больше за один ход.