Решение: Стратегии в игре с камнями
Два игрока, Петя и Ваня, играют в игру с кучей камней. Игроки ходят по очереди, первый ход делает Петя. За один ход можно добавить в кучу 1 или 3 камня либо увеличить количество камней в куче в 2 раза. Игра завершается, когда количество камней становится не менее 36. Побеждает игрок, сделавший последний ход. В начальный момент в куче было $S$ камней, где $1 \leq S \leq 35$. Игрок имеет выигрышную стратегию, если может выиграть при любых ходах противника.
Выполните задания: 1а) укажите все значения $S$, при которых Петя может выиграть одним ходом; 1б) укажите значение $S$, при котором Петя не может выиграть одним ходом, но после любого его хода Ваня выигрывает первым ходом, и опишите стратегию Вани. 2) укажите два значения $S$, при которых Петя не может выиграть одним ходом, но может гарантированно выиграть своим вторым ходом, и опишите его стратегию. 3) укажите значение $S$, при котором Ваня может гарантированно выиграть первым или вторым ходом, но не может гарантированно выиграть именно первым ходом. Опишите стратегию Вани и постройте дерево всех партий, возможных при этой стратегии.
Решение по шагам
9 шаговИгрок может выиграть одним ходом, если из текущей позиции можно получить не менее 36 камней. При $S<18$ это невозможно, поскольку даже удвоение даёт менее 36 камней. При $18\leq S\leq35$ удвоение приводит к позиции не менее 36.
$$2S\geq36\Longleftrightarrow S\geq18$$Следовательно, в задании 1а все значения $S$ имеют вид $18\leq S\leq35$.
Для $S=17$ Петя может получить позиции 18, 20 или 34. Из каждой из них Ваня выигрывает одним ходом удвоением. Поэтому Петя не выигрывает сразу, а Ваня выигрывает своим первым ходом после любого хода Пети.
$$17\to18,\ 20,\ 34$$Чтобы Петя гарантированно выиграл вторым ходом, ему нужно первым ходом перевести игру в позицию 17: из позиции 17 любой ход Вани даёт 18, 20 или 34, после чего Петя выигрывает удвоением.
$$14\xrightarrow{+3}17,\qquad16\xrightarrow{+1}17$$Таким образом, в задании 2 подходят $S=14$ и $S=16$. В обоих случаях Петя первым ходом получает 17, а затем отвечает на любой ход Вани удвоением: $18\to36$, $20\to40$, $34\to68$.
Для задания 3 подходит $S=4$. Петя не может выиграть первым ходом и может сделать ходы в позиции 5, 7 или 8. Ваня переводит их соответственно в позиции 10, 14 или 16.
$$4\to5\to10,\qquad4\to7\to14,\qquad4\to8\to16$$Из позиции 10 после ходов Пети 11, 13 или 20 Ваня удваивает количество камней и выигрывает. Из позиции 14 после ходов 15, 17 или 28 Ваня также удваивает количество камней. Из позиции 16 после ходов 17, 19 или 32 Ваня выигрывает удвоением.
$$10\to11,13,20;\quad14\to15,17,28;\quad16\to17,19,32$$Ваня не может гарантированно выиграть именно первым ходом при $S=4$, поскольку после хода Пети $4\to5$, $4\to7$ или $4\to8$ позиции 5, 7 и 8 ещё не позволяют Ване немедленно получить 36 камней. Однако после второго хода Вани выигрыш гарантирован.
Дерево партий при стратегии Вани: после $4\to5$ Ваня делает $5\to10$, после чего возможны $10\to11\to22$, $10\to13\to26$ и $10\to20\to40$. После $4\to7$ Ваня делает $7\to14$, после чего возможны $14\to15\to30$, $14\to17\to34$ и $14\to28\to56$. После $4\to8$ Ваня делает $8\to16$, после чего возможны $16\to17\to34$, $16\to19\to38$ и $16\to32\to64$.
1а) $S=18,19,\ldots,35$. 1б) $S=17$; Ваня после любого хода Пети получает позицию 18, 20 или 34 и выигрывает удвоением. 2) $S=14$ и $S=16$; Петя переводит игру в 17, после чего выигрывает следующим ходом при любом ответе Вани. 3) $S=4$; стратегия Вани: $5\to10$, $7\to14$, $8\to16$, затем удвоение после любого хода Пети. Дерево: $4\to5\to10\to11\to22$, $10\to13\to26$, $10\to20\to40$; $4\to7\to14\to15\to30$, $14\to17\to34$, $14\to28\to56$; $4\to8\to16\to17\to34$, $16\to19\to38$, $16\to32\to64$.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Указывать только одну позицию из диапазона $18\ldots35$ в задании 1а.
Считать, что при $S=17$ Петя может выиграть одним ходом.
Для задания 2 выбирать позиции 14 и 16, но не объяснять перевод в позицию 17.
Строить полное дерево игры вместо дерева партий, совместимых со стратегией Вани.
Не указывать ходы Вани после каждого возможного хода Пети.