Решение: Игра с кучей камней
Два игрока, Петя и Ваня, играют в игру с кучей камней. Первый ход делает Петя. За один ход можно добавить в кучу 1 или 4 камня либо увеличить количество камней в 5 раз. Игра заканчивается, когда количество камней становится не менее 63. Побеждает игрок, сделавший последний ход. В начальный момент в куче было $S$ камней, где $1 \leq S \leq 62$. Во всех случаях обоснуйте ответ.
Выполните три задания: определите значения $S$ для выигрыша Пети за один ход; найдите стратегии Вани и Пети для указанных условий; для задания 3 постройте дерево всех партий, возможных при реализации стратегии Вани.
Решение по шагам
8 шаговЕсли в куче не менее $13$ камней, игрок может умножить количество камней на 5 и получить не менее $65$. Поэтому Петя выигрывает за один ход при всех $13 \leq S \leq 62$.
$$5S \geq 63 \Longleftrightarrow S \geq 13$$Для меньших значений последовательно определяем проигрышные позиции. Позиция проигрышная, если все возможные ходы переводят её в выигрышную позицию.
$$L=\{1,4,7,9,10,12\}$$Задание 1б: можно взять $S=12$. Петя после любого хода получает соответственно $13$, $16$ или $60$. В каждой из этих позиций Ваня умножает количество камней на 5 и получает не менее $63$.
$$12\to13,16,60;\qquad 13\cdot5,16\cdot5,60\cdot5\geq63$$Задание 2: подходят, например, $S=6$ и $S=11$. При $S=6$ Петя переводит игру в $7$ или $10$, после чего любой ход Вани переводит игру в выигрышную для Пети позицию. При $S=11$ Петя единственным безусловно выигрышным ходом получает $12$.
$$6\to7\text{ или }10;\qquad 11\to12$$Из позиции $6$ стратегия Пети: сделать ход $+1$ и получить $7$ либо сделать ход $+4$ и получить $10$. После любого хода Вани Петя выполняет ход, который приводит к позиции не менее $13$ или непосредственно к завершению игры.
$$6+1=7,\qquad 6+4=10$$Из позиции $11$ стратегия Пети состоит в переходе к $12$. После хода Вани из $12$ возможны позиции $13$, $16$ и $60$, из каждой из которых Петя выигрывает следующим ходом.
$$11+1=12;\qquad 12\to13,16,60$$Для задания 3 подходит $S=2$. После первого хода Пети возможны позиции $3$, $6$ и $10$. В позициях $3$ и $6$ Ваня переводит игру в позиции $7$ и $10$ соответственно, а из позиции $10$ переводит игру в $50$. После следующего хода Пети Ваня завершает игру умножением на 5.
$$2\to3,6,10;\qquad 3\to7,\quad6\to10,\quad10\to50$$Ветви дерева стратегии Вани: $2\xrightarrow{П}3\xrightarrow{В}7$; $2\xrightarrow{П}6\xrightarrow{В}10$; $2\xrightarrow{П}10\xrightarrow{В}50$. После этих переходов Ваня выбирает ход, который приводит к числу не менее $63$.
Задание 1: а) $13\text{–}62$; б) например, $S=12$. Задание 2: например, $S=6$ и $S=11$. Задание 3: $S=2$.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Считать выигрышной любую позицию, из которой существует хотя бы один удачный ход, не проверяя все возможные ходы противника.
Забывать, что игра завершается сразу после получения не менее $63$ камней.
Включать в стратегию ходы, которые не являются безусловно выигрышными.
Строить полное дерево игры вместо дерева, соответствующего выбранной выигрышной стратегии.