Шешімі: Выигрышная стратегия в игре
Два игрока, Петя и Ваня, играют в игру с кучей камней. Первый ход делает Петя. За один ход можно убрать 3 или 5 камней либо уменьшить количество камней в 4 раза, округлив результат вниз. Игра завершается, когда в куче становится не более 10 камней; победителем считается игрок, сделавший последний ход. В начальный момент в куче было $S$ камней, $S \ge 11$. Укажите минимальное значение $S$, при котором Петя не может выиграть за один ход, но после любого хода Пети Ваня может выиграть своим первым ходом.
Шешімін қадамдап көрсету
3 қадамПетя не должен иметь возможности закончить игру первым ходом. Поэтому после любого его хода количество камней должно быть больше 10.
$$S-3>10,\quad S-5>10,\quad \left\lfloor\frac{S}{4}\right\rfloor>10$$Первые два неравенства дают $S>13$ и $S>15$. Условие с делением выполняется при $S\ge 44$, так как при $S=43$ результат деления равен $10$, а при $S=44$ — $11$.
$$\left\lfloor\frac{43}{4}\right\rfloor=10,\quad \left\lfloor\frac{44}{4}\right\rfloor=11$$Проверим позицию $S=44$. После ходов Пети количество камней может стать $41$, $39$ или $11$. Из позиции $41$ Ваня делением получает $10$, из позиции $39$ — $9$, а из позиции $11$ удалением 3 камней получает $8$.
Где здесь ошибаются
Проверяют только возможность хода с делением на 4 и не рассматривают ходы с удалением 3 и 5 камней.
Забывают, что округление при делении выполняется вниз.
Считают выигрышной позицию, в которой после хода остаётся ровно 10 камней: такая позиция уже завершает игру.