Решение: Выигрышная стратегия в игре
Документ к заданиюИнструкция к заданиям по информатике
Прочитайте текст и выполните задания.
Два игрока, Петя и Ваня, играют в игру с кучей камней. За один ход можно добавить 1 или 4 камня либо увеличить количество камней в два раза. Игра заканчивается, когда в куче становится не менее 31 камня. В начальный момент в куче было $S$ камней, где $1 \le S \le 30$.
Укажите такое значение $S$, при котором Петя не может выиграть за один ход, но после любого первого хода Пети Ваня может выиграть своим первым ходом. Общий текст задачи приведён в отдельном материале.
Решение по шагам
4 шагаПетя не может выиграть первым ходом, если после прибавления 1 или 4, а также после удвоения количество камней меньше 31. Для $S \le 15$ это условие выполняется.
Ваня может выиграть одним ходом из любой позиции с количеством камней не менее 16: достаточно удвоить количество камней, поскольку $2 \cdot 16 = 32 \ge 31$.
После любого хода Пети из позиции $S$ получаются значения $S+1$, $S+4$ и $2S$. Все они должны быть не менее 16. Наиболее строгим является условие $S+1 \ge 16$, откуда $S \ge 15$.
Совместно с условием $S \le 15$ получаем единственное значение $S=15$. После ходов Пети возможны позиции 16, 19 и 30, и Ваня в каждом случае удваивает количество камней.
Где здесь ошибаются
Проверяют только возможность удвоения и не учитывают ходы с прибавлением 1 или 4.
Берут позицию $S=16$, забывая, что тогда Петя сам может сразу получить не менее 31 камня удвоением.
Требуют, чтобы после хода Пети получилось ровно 16, хотя достаточно любого количества не менее 16.