Два игрока, Паша и Вова, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в три раза. Например, пусть в одной куче 20 камней, а в другой — 10 камней; такую позицию в игре будем обозначать (20, 10). Тогда за один ход можно получить любую из четырёх позиций: (21, 10), (60, 10), (20, 11), (20, 30).
Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 167. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, что в кучах всего будет 167 или больше камней. В начальный момент в первой куче было 40 камней, во второй куче—S камней; 1 ≤ S ≤ 160.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока—значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания. Во всех случаях обосновывайте свой ответ.
Задание 1. а) Укажите все такие значения числа S, при которых Паша может выиграть за один ход и соответствующие выигрышные ходы. Если при некотором значении S Паша может выиграть несколькими способами, достаточно указать один выигрышный ход.
б) Укажите, сколько существует значений S, при которых Паша не может выиграть за один ход, но при любом ходе Паши Вова может выиграть своим первым ходом. Опишите выигрышную стратегию Вовы.
Задание 2. Укажите такое значение S, при котором у Паши есть выигрышная стратегия, причём одновременно выполняются два условия:
—Паша не может выиграть за один ход;
—Паша может выиграть своим вторым ходом независимо от того, как будет ходить Вова.
Для указанного значения S опишите выигрышную стратегию Паши.
Задание 3. Укажите значение S, при котором одновременно выполняются два условия:
— у Вовы есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Паши;
—у Вовы нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Вовы.
Постройте дерево всех партий, возможных при этой выигрышной стратегии Вовы (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах—количество камней в куче.
В заданиях 2 и 3 достаточно указать одно значение S и объяснить, почему это значение удовлетворяет условию соответствующего задания.
Пусть S —исходное количество камней во второй куче.
Задание 1. a) Паша может выиграть первым ходом, если S ∈ {43, 44, . . . , 160}.
Во всех случаях ему нужно удвоить количество камней во второй куче.
Если количество камней во второй куче меньше 43, то за один ход нельзя получить суммарное число камней в двух кучах более 166.
Задание 1. б) Вова может выиграть первым ходом (как бы ни играл Паша), если исходно во второй куче будет S = 42 камня, то есть начальной будет позиция (40, 42), то после первого хода Паши может получиться одна из четырёх позиций: (41, 42)— всего 83, (120, 42)—всего 162, (40, 43)—всего 83, (40, 126)— всего 166.
В каждом из полученных случаев суммарное число камней меньше, чем 169. Значит, Паша не может выиграть своим первым ходом. Для каждой из полученных позиций Вова, утроив число камней во второй куче, получит соответственно позиции (41, 126)—всего 167, (120, 126)—всего 246, (40, 129)—всего 169, (40, 378) — всего 418. В каждом случае суммарное число камней не менее 167. Следовательно, Вова выигрывает своим первым ходом.
Задание 2. Возможное значение S = 41. Если начальная позиция (40, 41), то Паша, чтобы выиграть своим вторым ходом, должен получить позицию (40, 42). Для этого ему нужно в кучу с 42 камнями добавить один камень. Считая позицию (40, 42) начальной, мы приходим к рассмотрению ситуации задания 1б.
При такой начальной позиции выигрывает второй игрок своим первым ходом. Значит, если начальной позицией будет (40, 41), то выиграет Паша своим вторым ходом.
Задание 3. Возможное значение S = 40. Если начальная позиция (40, 40), то после первого хода Паши может получиться одна из четырёх позиций: (40, 41), (41, 40) — всего 81, (120, 40), (40, 120)—всего 160.
Если после хода Паши получены позиции (120, 40), (40, 120), то Вова, утроив число камней в куче со 120 камнями, получит позицию с суммарным числом камней, равным 400, и выиграет своим первым ходом.
Если после хода Паши получены позиции (40, 41), (41, 40), то Вова, увеличив в одной из куч число камней на 1, получит позиции (40, 42) или (42, 40) и, как было показано в ответе к заданию 1б, выиграет своим вторым ходом.
В таблице изображено дерево возможных партий при описанной стратегии Вовы. Заключительные позиции (в них выигрывает Вова) подчёркнуты.
| И. п. | Положение после очередных ходов | |||
| 1-й ход Паши (разобраны все ходы) |
1-й ход Вовы (только ход по стратегии) |
2-й ход Паши (разобраны все ходы) |
2-й ход Вовы (только ход по стратегии) |
|
| (40, 40) | (40, 41) | (40, 42) | (120, 42) | (120, 126) |
| (41, 42) | (41, 126) | |||
| (40, 126) | (40, 378) | |||
| (40, 43) | (40, 129) | |||
| (41, 40) | (42, 41) | (42, 120) | (126, 120) | |
| (42, 41) | (126, 41) | |||
| (126, 40) | (378, 40) | |||
| (43, 40) | (129, 40) | |||
| (120, 40) | (120, 120) | |||
| (40, 120) | (120, 120) | |||