Решение: Стратегия в игре с камнями
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может убрать из кучи 3 камня, убрать из кучи 7 камней или уменьшить количество камней в куче в 4 раза; количество камней, полученное при делении, округляется до меньшего. Например, из кучи в 20 камней за один ход можно получить кучу из 17, 13 или 5 камней. Игра завершается, когда количество камней в куче становится не более 15. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 15 или менее камней. В начальный момент в куче было $S$ камней, $S \ge 16$. Укажите минимальное значение $S$, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Решение по шагам
4 шагаПосле хода Пети количество камней должно оставаться больше 15, иначе Петя сразу выиграет.
$$S-3>15,\quad S-7>15,\quad \left\lfloor S/4 \right\rfloor>15$$Наиболее строгое условие задаёт деление на 4: результат должен быть не меньше 16.
$$\left\lfloor S/4 \right\rfloor\ge 16 \Rightarrow S\ge 64$$При $S=64$ Петя может получить 61, 57 или 16 камней. Из 61 и 57 Ваня делит количество камней на 4 и получает соответственно 15 и 14 камней, а из 16 камней убирает 3 и получает 13 камней.
Следовательно, при любом ходе Пети Ваня выигрывает своим первым ходом, а значение $S=64$ является минимальным.
Где здесь ошибаются
Проверяют только ходы с уменьшением на 3 и 7, но забывают деление на 4.
Считают, что при $S=64$ Петя может сразу выиграть делением, хотя получается 16 камней, то есть игра ещё не заканчивается.
Не проверяют все три возможных хода Пети.