Решение: Выигрышная стратегия в игре
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может убрать из кучи 3 камня, убрать из кучи 5 камней или уменьшить количество камней в куче в 4 раза, при этом количество камней, полученное при делении, округляется до меньшего. Например, из кучи в 20 камней за один ход можно получить кучу из 17, 15 или 5 камней.
Игра завершается, когда количество камней в куче становится не более 30. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 30 или менее камней. В начальный момент в куче было $S$ камней, $S \ge 31$.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное значение $S$, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Решение по шагам
3 шагаПетя не должен выигрывать своим первым ходом, поэтому после каждого его хода количество камней должно оставаться больше 30. Для $S=124$ возможны позиции $121$, $119$ и $31$.
$$124-3=121,\quad 124-5=119,\quad \left\lfloor\dfrac{124}{4}\right\rfloor=31$$Из каждой полученной позиции Ваня может сделать ход, после которого в куче будет не более 30 камней.
$$121\to\left\lfloor\dfrac{121}{4}\right\rfloor=30,\quad 119\to\left\lfloor\dfrac{119}{4}\right\rfloor=29,\quad 31\to31-3=28$$Следовательно, после любого хода Пети Ваня выигрывает своим первым ходом. Проверка меньших значений $S\ge31$ показывает, что это условие впервые выполняется при $S=124$.
Где здесь ошибаются
Проверяют только один из возможных ходов Пети.
Забывают, что при делении количество камней округляется вниз.
Считают выигрышной позицию, в которой Петя сам сразу получает не более 30 камней.