Перейти к содержанию

В начальный момент времени в куче находилось 1 ≤ S ≤ 44 камней

Два игрока, Коля и Саша, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Коля. В начальный момент времени в куче находилось 1 ≤ S ≤ 44 камней. За один ход игрок может добавить в кучу два камня или увеличить количество камней в куче в два раза. Игра завершается, когда в куче становится не менее 46 камней. При этом если в куче будет не более 68 камней, то побеждает тот игрок, который сделал последний ход, в противном случае побеждает другой игрок.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока—значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.

Выполните следующие задания.

Задание 1. а) Найдите все значения S, при которых Коля может выиграть первым ходом. Укажите все такие значения и соответствующие ходы Коли.

б) Определите, кто из игроков имеет выигрышную стратегию при S = 42, S = 40, S = 38. Опишите выигрышные стратегии для этих случаев.

Задание 2. Определите, кто из игроков имеет выигрышную стратегию при S = 21, S = 19. Опишите соответствующие выигрышные стратегии.

Задание 3. Определите, кто из игроков имеет выигрышную стратегию при S = 17. Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход; в узлах—количество камней в позиции.


Задание 1. а) Коля может выиграть первым ходом, если S ∈ {23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 44}.

Для S ∈ {23, 24, . . . , 34} ему нужно удвоить количество камней. Для S = 44—добавить два камня.

Для других значений S Коля либо наберёт менее 46 камней, либо наберёт более 68 камней.

б) При S = 42 выигрывает Саша (второй игрок) своим первым ходом. Если Коля удвоит число камней, то в куче станет 84 (= 42 ∗ 2) камня. Так как 84 > 68, то победит игрок, не сделавший последний ход, то есть Саша. Если Коля добавит в кучу два камня, то в куче станет 44 камня. В этом случае Саша (второй игрок), добавив два камня, получит 46 камней и выиграет своим первым ходом.

При S = 40 выиграет Коля (первый игрок) своим вторым ходом. Для выигрыша Коле следует первым ходом добавить в кучу два камня. Тогда в куче станет 42 камня. Как показано выше, в этом случае выиграет тот из игроков, который ходит вторым, то есть Коля.

При S = 38 выиграет Саша (второй игрок) своим вторым ходом.

Если Коля удвоит число камней, то в куче станет 76 (= 38 · 2) камней. Так как 76 > 68, то победит игрок, не сделавший последний ход, то есть Саша. Если Коля добавит в кучу два камня, то в куче станет 40 камней. Как показано выше, в этом случае выиграет тот из игроков, который ходит первым, то есть Саша.

Задание 2. Если S = 21, то выигрывает Коля (первый игрок).

Для этого ему следует удвоить число камней, тогда в куче станет 42 (= 21 ∗ 2) камня. Стратегия игры для данной позиции была рассмотрена в задании 1.

Если S = 19, то выигрывает Коля (первый игрок). Для выигрыша Коле следует первым ходом удвоить число камней. Тогда в куче станет 38 камней. Как показано выше, в этом случае выигрывает тот из игроков, который делает ход вторым, то есть Коля.

Задание 3. Если S = 17, то выигрывает Саша (второй игрок).

Первым ходом Коля может получить либо 19 (= 17 + 2) камней, либо 34 (= 17 · 2) камня. В случае если он получит 19 камней, то Саша выиграет либо вторым, либо третьим ходом, что следует из задания 2. В случае, если Коля получит 34 камня, то Саша выиграет первым ходом, удвоив количество камней в куче.

Таблица выигрышных стратегий для S = 17. Заключительные позиции (в них выигрывает Саша) подчёркнуты.

  К С К С К С
S = 17 19 38 40 42 44 46 победа
84 победа
76 победа    
34 68 победа