Решение: Выигрышная стратегия в игре
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может убрать из кучи 2 камня, убрать из кучи 4 камня или уменьшить количество камней в куче в 4 раза; количество камней, полученное при делении, округляется до меньшего. Например, из кучи в 20 камней за один ход можно получить кучу из 18, 16 или 5 камней.
Игра завершается, когда количество камней в куче становится не более 23. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 23 или менее камней. В начальный момент в куче было $S$ камней, $S \ge 24$.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное значение $S$, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Решение по шагам
3 шагаПетя выигрывает за один ход, если после одного из его ходов в куче останется не более 23 камней. Для деления на 4 это выполняется при $\lfloor S/4 \rfloor \le 23$, то есть при $S \le 95$. Поэтому минимальное значение, при котором Петя уже не может выиграть сразу, начинается с $S=96$.
$$\left\lfloor \frac{S}{4} \right\rfloor \le 23 \text{ при } S \le 95$$Проверим значение $S=96$. После ходов Пети возможны кучи из $94$, $92$ и $24$ камней.
Если осталось 94 или 92 камня, Ваня делит количество камней на 4 и получает 23 камня. Если осталось 24 камня, Ваня также делит кучу на 4 и получает 6 камней. Во всех случаях Ваня получает кучу не более 23 камней и выигрывает своим первым ходом.
$$\left\lfloor \frac{94}{4} \right\rfloor=23,\quad \left\lfloor \frac{92}{4} \right\rfloor=23,\quad \left\lfloor \frac{24}{4} \right\rfloor=6$$Где здесь ошибаются
Проверяют только один возможный ход Пети, а не все три.
Забывают, что результат деления округляется вниз.
Выбирают значение меньше 96, не учитывая, что при $S \le 95$ Петя может сразу разделить кучу на 4.