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

Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 62

Два игрока, Коля и Саша, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Коля. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 20 камней, а в другой — 10 камней; такую позицию в игре будем обозначать (20, 10). Тогда за один ход можно получить любую из четырёх позиций: (21, 10), (40, 10), (20, 11), (20, 20).

Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 62. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, что в кучах всего будет 62 или больше камней. В начальный момент в первой куче было 19 камней, во второй куче—S камней; 1 ≤ S ≤ 60. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока—значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.

Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

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

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

Задание 2. Укажите такое значение S, при котором у Коли есть выигрышная стратегия, причём одновременно выполняются два условия:

—Коля не может выиграть за один ход;

—Коля может выиграть своим вторым ходом независимо от того, как будет ходить Саша.

Для указанного значения S опишите выигрышную стратегию Коли.

Задание 3. Укажите значение S, при котором одновременно выполняются два условия:

— у Саши есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Коли;

—у Саши нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

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

В заданиях 2 и 3 достаточно указать одно значение S и объяснить, почему это значение удовлетворяет условию соответствующего задания.


Пусть S —исходное количество камней во второй куче.

Задание 1. a) Коля может выиграть первым ходом, если S ∈ {22, 23, . . . , 60}. Во всех случаях ему нужно удвоить количество камней во второй куче. Если количество камней во второй куче меньше 22, то за один ход нельзя получить суммарное число камней в двух кучах более 62.

б) Саша может выиграть первым ходом (как бы ни играл Коля), если исходно во второй куче будет S = 21 камень, то есть начальной будет позиция (19, 21), то после первого хода Коли может получиться одна из четырёх позиций: (19, 22) — всего 41, (20, 21) — всего 41, (38, 21) — всего 59, (19, 42) — всего 61. В каждом из полученных случаев суммарное число камней не превышает 62. Значит, Коля не может выиграть своим первым ходом. Для каждой из полученных позиций Саша, удвоив число камней во второй куче, получит соответственно позиции (19, 44) — всего 63, (20, 42) — всего 62, (38, 42) — всего 80, (19, 84)—всего 103.

В каждом случае суммарное число камней не менее 62. Следовательно, Саша выигрывает своим первым ходом.

Задание 2. Возможное значение S = 20. Если начальная позиция (19, 20), то Коля, чтобы выиграть своим вторым ходом, должен получить позицию (19, 21). Для этого ему нужно в кучу с 20 камнями добавить один камень. Считая позицию (19, 21) начальной, мы приходим к рассмотрению ситуации задания 1б.

При такой начальной позиции выигрывает второй игрок своим первым ходом. Значит, если начальной позицией будет (19, 20), то выиграет Коля своим вторым ходом.

Задание 3. Возможное значение S = 19. Если начальная позиция (19, 19), то после первого хода Коли может получиться одна из четырёх позиций: (20, 19), (19, 20) — всего 39, (38, 19), (19, 38) — всего 57. Если после хода Коли получены позиции (19, 38), (38, 19), то Саша, удвоив число камней в куче с 38 камнями, получит позицию с суммарным числом камней, равным 95, и выиграет своим первым ходом. Если после хода Коли получены позиции (20, 19), (19, 20), то Саша, увеличив в куче с 20 камнями их число на 1, получит позиции (21, 19) или (19, 21) и, как было показано в ответе к заданию 1б, выиграет своим вторым ходом. В таблице изображено дерево возможных партий при описанной стратегии Саши. Заключительные позиции (в них выигрывает Саша) подчёркнуты.

И. п. Положение после очередных ходов
1-й ход Коли
(разобраны все ходы)
1-й ход Саши
(только ход по стратегии)
2-й ход Коли
(разобраны все ходы)
2-й ход Саши
(только ход по стратегии)
(19, 19) (19, 20) (19, 21) (19, 22) (19, 44)
  (20, 21) (20, 42)
(19, 42) (19, 84)
(38, 21) (38, 42)
(20, 19) (21, 19) (22, 19) (44, 19)
(21, 20) (42, 20)
(42, 19) (84, 19)
(21, 38) (42, 38)
(38, 19) (76, 19)    
(19, 38) (19, 76)