Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
увеличить количество камней в куче в два раза или увеличить количество камней в куче в три раза.
Например, имея кучу из 10 камней, за один ход можно получить кучу из 20 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче превышает 49. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 50 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 49.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы следующего стратегии игрока, которые не являются для него безусловно выигрышными.
Выполните следующие задания.
Задание 1. Назовите все значения S, при которых Петя может выиграть первым ходом, причём у Пети есть ровно один выигрывающий ход.
Задание 2. Назовите все значения S, при которых Ваня может выиграть первым ходом, независимо от того, каким будет первый ход Пети. Опишите выигрышную стратегию Вани для этих значений S.
Задание 3. Назовите все значения S, при которых Петя не может выиграть первым ходом, но может выиграть вторым ходом независимо от того, как будет играть Ваня, причём в начальной позиции у Пети есть ровно один выигрывающий ход. Опишите выигрышную стратегию Пети для всех этих значений. Постройте (в виде рисунка или таблицы) дерево всех партий, возможных при этой стратегии для одного произвольного значения S. На рёбрах дерева указывайте, кто делает ход, в узлах – количество камней в позиции. Дерево должно содержать только те партии, которые возможны при реализации выигрышной стратегии Пети.
Задание 1. Петя может выиграть единственным первым ходом, если S = 17, …, 24. Для выигрыша необходимо утроить количество камней. При меньших значениях S за один ход нельзя получить кучу, в которой будет 50 или более камней. При бо́льших значениях S Петя тоже выигрывает первым ходом, но сделать это можно двумя способами (удвоением и утроением)
Задание 2. Ваня выигрывает первым ходом при S от 9 до 16. После хода Пети в куче станет от 18 до 48 камней. В любом из этих случаев Ваня может утроить количество камней и выиграть.
Задание 3. Чтобы выиграть вторым ходом, Петя должен сделать так, чтобы после его первого хода в куче было от 9 до 16 камней. Эти позиции разобраны в задании 2, в них игрок, который будет ходить (теперь это Ваня), проигрывает. Петя может получить такую кучу единственным способом при S = 3, 4, 6, 7, 8. При S = 3 и S = 4 Петя должен первым ходом утроить количество камней, в остальных случаях – удвоить. После этого в куче будет от 9 до 16 камней, после ответного хода Вани Петя может утроить количество камней и выиграть. Значение S = 5 не входит в список, так как в этом случае у Пети есть два выигрывающих хода.
В таблице изображено дерево возможных партий при описанной стратегии Пети для S = 6. Заключительные позиции (в них выигрывает Петя) подчёркнуты. На рисунке это же дерево изображено в графическом виде (оба способа изображения дерева допустимы). Для других значений S дерево строится аналогично.
| Исходное положение | 1-й ход Пети (только ход по стратегии) | 1-й ход Вани (разобраны все ходы) | 2-й ход Пети (только ход по стратегии) |
|---|---|---|---|
| 6 | 6*2 = 12 | 12*2 = 24 | 24*3 = 72 |
| 12*3 = 36 | 36 * 3 = 108 |
Рис. 1. Дерево всех партий, возможных при описанной стратегии Пети. Ходы Пети показаны сплошными стрелками, ходы Вани – пунктирными стрелками. Заключительные позиции обозначены знаком >>.