Решение: Выигрышная стратегия в игре
Документ к заданиюИнструкция к заданиям по информатике
Прочитайте текст и выполните задания.
Два игрока, Петя и Ваня, играют в игру с кучей камней. За один ход игрок может добавить в кучу 1 или 4 камня либо увеличить количество камней в куче в 3 раза. Первый ход делает Петя. Игра заканчивается, когда в куче становится не менее 43 камней. В начальный момент в куче было $S$ камней, где $1 \leq S \leq 42$. Укажите такое значение $S$, при котором Петя не может выиграть за один ход, но после любого хода Пети Ваня может выиграть своим первым ходом.
Решение по шагам
4 шагаПетя не должен иметь возможности закончить игру одним ходом. Поэтому должны выполняться условия $S+1<43$, $S+4<43$ и $3S<43$. Наиболее сильное из них даёт $S \leq 14$.
Проверим значение $S=14$. После ходов Пети количество камней может стать равным 15, 18 или 42.
Из 15 камней Ваня умножением на 3 получает 45 камней; из 18 камней умножением на 3 получает 54 камня; из 42 камней добавлением 1 получает 43 камня.
Следовательно, после любого первого хода Пети Ваня выигрывает своим первым ходом, а Петя сам не может выиграть за один ход.
Где здесь ошибаются
Проверяют только возможность хода $S \to 3S$ и забывают ходы с добавлением 1 и 4 камней.
Не проверяют, что Ваня должен выигрывать после каждого возможного хода Пети.