Решение: Стратегии в игре с камнями
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда количество камней в куче становится не менее 65. Побеждает игрок, сделавший последний ход. В начальный момент в куче было $S$ камней, $1 \leq S \leq 64$.
Выполните следующие задания. Во всех случаях обосновывайте ответ.
Задание 1. Укажите все такие значения $S$, при которых Петя может выиграть в один ход, и соответствующие выигрывающие ходы. Укажите такое значение $S$, при котором Петя не может выиграть за один ход, но после любого его хода Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.
Задание 2. Укажите два значения $S$, при которых Петя не может выиграть за один ход, но может выиграть своим вторым ходом независимо от хода Вани. Для каждого значения опишите выигрышную стратегию Пети.
Задание 3. Укажите значение $S$, при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, но нет стратегии, позволяющей гарантированно выиграть первым ходом. Опишите стратегию Вани. Постройте дерево всех партий, возможных при этой стратегии Вани: на рёбрах укажите ходы, в узлах — позиции.
Решение по шагам
6 шаговИгрок выигрывает одним ходом, если после прибавления одного камня или удвоения количество камней становится не менее 65. При $S \geq 33$ достаточно удвоения. При $S=64$ можно также прибавить один камень.
$$2S \geq 65 \Rightarrow S \geq 33; \qquad S+1 \geq 65 \Rightarrow S=64$$Для задания 1б подходит $S=32$: Петя не может выиграть сразу, но после его хода получаются позиции $33$ или $64$, из которых Ваня выигрывает одним ходом.
Для задания 2 Петя должен перевести игру в позицию $31$. Из позиции $31$ любой ход Вани даёт $32$ или $62$, после чего Петя выигрывает: из $32$ он удваивает кучу до $64$? Нет, поэтому корректный анализ требует учитывать непосредственную победу следующим ходом: из $31$ Ваня получает $32$ или $62$, а Петя из $32$ удваивает до $64$ и затем игра не завершается. Следовательно, целевой позицией является $32$: из неё любой ход Вани даёт $33$ или $64$, и Петя выигрывает сразу.
$$15 \xrightarrow{\times 2} 30,\quad 30 \xrightarrow{+1}31$$Корректная стратегия задания 2: Петя переводит игру в позицию $32$ из позиций $16$ или $31$. Из $16$ он удваивает кучу, а из $31$ прибавляет один камень. После этого любой ход Вани приводит к $33$ или $64$, и Петя выигрывает следующим ходом.
$$16 \xrightarrow{\times 2}32; \qquad 31\xrightarrow{+1}32$$Для задания 3 подходит $S=29$. Если Петя получает $30$ прибавлением одного камня, Ваня получает $31$ прибавлением одного камня. Если Петя получает $58$ удвоением, Ваня получает $59$ прибавлением одного камня. После этого любой ход Пети позволяет Ване завершить игру следующим ходом.
В позиции $29$ Ваня не может гарантировать победу первым ходом: если Петя увеличит кучу до $30$, Ваня не получает сразу не менее 65 камней. Но Ваня гарантированно выигрывает первым или вторым ходом по описанной стратегии.
1а) $S=33,34,\ldots,64$: выигрыш удвоением; при $S=64$ также можно прибавить один камень. 1б) $S=32$: после хода Пети Ваня получает $33$ или $64$ и выигрывает следующим ходом. 2) $S=16$ и $S=31$: Петя переводит игру в $32$, после чего выигрывает после любого хода Вани. 3) $S=29$: Ваня отвечает переводом в $31$ или $59$, после чего выигрывает не позднее своего второго хода.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Считать позицию $32$ проигрышной, хотя из неё можно получить $64$, а затем победить прибавлением одного камня.
Забывать, что игра заканчивается сразу после получения 65 или более камней.
Для задания 2 выбирать позиции, из которых нельзя перевести игру именно в $32$.
Не рассматривать оба возможных хода соперника при построении стратегии.