Шешімі: Выигрышная стратегия в игре
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может убрать из кучи 3 камня, убрать из кучи 8 камней или уменьшить количество камней в куче в 3 раза; количество камней, полученное при делении, округляется до меньшего. Например, из кучи в 20 камней за один ход можно получить кучу из 17, 12 или 6 камней.
Игра завершается, когда количество камней в куче становится не более 16. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 16 или менее камней. В начальный момент в куче было $S$ камней, $S \ge 17$.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное значение $S$, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Шешім по шагам
5 қадамПетя не должен иметь возможности закончить игру своим первым ходом. Поэтому результат каждого возможного хода Пети должен быть больше 16.
$$S-3>16,\quad S-8>16,\quad \left\lfloor\frac{S}{3}\right\rfloor>16$$Наиболее строгое ограничение даёт ход с делением на 3:
$$\left\lfloor\frac{S}{3}\right\rfloor>16\Rightarrow S\ge 51$$Проверим значение $S=51$. После ходов Пети получаются кучи размером $48$, $43$ и $17$.
$$51-3=48,\quad 51-8=43,\quad \left\lfloor\frac{51}{3}\right\rfloor=17$$Из каждой из этих позиций Ваня может выиграть своим первым ходом: из 48 убрать 8 камней, из 43 убрать 8 камней, из 17 убрать 3 камня.
$$48-8=40\text{ — нет}$$Уточним выигрышные ходы Вани: из 48 разделить кучу на 3 и получить 16, из 43 убрать 8 камней и получить 35 — это не подходит; вместо этого разделить на 3 и получить 14, из 17 убрать 3 камня и получить 14.
$$\left\lfloor\frac{48}{3}\right\rfloor=16,\quad \left\lfloor\frac{43}{3}\right\rfloor=14,\quad 17-3=14$$Где здесь ошибаются
Проверяют только ходы с вычитанием и забывают ход с делением на 3.
Считают, что после хода Пети достаточно получить любую позицию меньше 51, не проверяя возможность немедленного выигрыша Вани.
Не учитывают округление результата деления вниз.