Два игрока, Коля и Саша, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Коля. В начальный момент времени в куче находилось 1 ≤ S ≤ 53 камней. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в три раза. Игра завершается, когда в куче становится не менее 54 камней. При этом если в куче будет не более 84 камней, то побеждает тот игрок, который сделал последний ход, в противном случае побеждает его соперник.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока—значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания.
Задание 1. а) Найдите все значения S, при которых Коля может выиграть первым ходом. Укажите все такие значения и соответствующие ходы Коли.
б) Определите, кто из игроков имеет выигрышную стратегию при S = 50, S = 51, S = 52. Опишите выигрышные стратегии для этих случаев.
Задание 2. Определите, кто из игроков имеет выигрышную стратегию при S = 16, S = 48. Опишите соответствующие выигрышные стратегии.
Задание 3. Определите, кто из игроков имеет выигрышную стратегию при S = 14. Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход; в узлах—количество камней в позиции.
Задание 1. а) Коля может выиграть первым ходом, если S ∈ {18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 53}.
Для S ∈ {18, 19, . . . , 28} ему нужно утроить количество камней. Для S = 53—добавить один камень.
Если количество камней меньше 18 или больше 28, то за один ход Коля выиграть не может.
б) При S = 52 выигрывает Саша (второй игрок) своим первым ходом. Если Коля утроит число камней, то в куче станет 156 (= 52 · 3) камней. Так как 156 > 84, то победит игрок, не сделавший последний ход, то есть Саша. Если Коля добавит в кучу один камень, то в куче станет 53 камня. В этом случае Саша (второй игрок), добавив один камень, получит 54 камня и выиграет своим первым ходом.
При S = 51 выиграет Коля (первый игрок) своим вторым ходом. Для выигрыша Коле следует добавить в кучу один камень.
Тогда в куче станет 52 камня. Как показано выше, в этом случае выиграет тот из игроков, который ходит вторым, то есть Коля.
При S = 50 выиграет Саша (второй игрок) своим вторым ходом. Если Коля утроит число камней, то в куче станет 150 (= 50 · 3) камней. Так как 150 > 84, то победит игрок, не сделавший последний ход, то есть Саша. Если Коля добавит в кучу один камень, то в куче станет 51 камень. Как показано выше, в этом случае выиграет тот из игроков, который ходит первым, то есть Саша.
Задание 2. Если S = 48, то выигрывает Саша (второй игрок).
Если Коля утроит число камней, то в куче станет 144 (= 48 · 3) камня. Так как 144 > 84, то победит игрок, не сделавший последний ход, то есть Саша. Если Коля добавит в кучу один камень, то в куче станет 49 камней. Саша, добавив в кучу один камень, получит 50 камней. Как показано выше, в этом случае выиграет тот из игроков, который ходит вторым, то есть Саша.
Если S = 16, то выигрывает Коля (первый игрок). Если Коля утроит число камней, то в куче станет 48 (= 16 · 3) камней. Как показано выше, в этом случае выигрывает тот из игроков, который делает ход вторым, то есть Коля.
Задание 3. Если S = 14, то выигрывает Коля (первый игрок).
На рисунке представлено дерево выигрышных стратегий для S = 14. Заключительные позиции (в них выигрывает Коля) указаны жирным шрифтом. Дерево содержит только выигрышные ходы для Коли и все ходы Саши.