Разбор задачи C3 (демо ЕГЭ 2006)
Введем обозначения:
х - первая куча,
у - вторая куча.
Старт: (х, у).
Варианты хода игроков: (х*2,у), (х,у*2), (х+4,у), (х, у+4).
Игрок выйграет, когда число камней в 2-х кучах станет ≥22 (х+у≥22). Изобразим ход игры в виде дерева решений. Необходимо ветвить дерево до того момента, когда все варианты последнего хода станут выйгрышными.
После первого хода дерево будет выглядеть так:
На дереве изображены все возможные варианты ходов.
После первых 2-х ходов дерево будет выглядеть так:
Одним цветом в строке подчертнуты одинаковые значения количества камней в кучах. По ходу игры будем ветвить только разные координаты.
Когда 2-й игрок совершает 2-й ход, он выигрывает, когда попадает в позицию: (20,3), т.к. сумма х и у в этих случаях больше 22. На рисунке выйгрышная позиция 2-го игрока выделена сплошной рамкой.
Мы не рассматривали остальные позиции (обозначены как "..."), если встречали выйгрышную позицию. Игроки играют безошибочно, поэтому 2-й игрок пойдет только по выйгрышной ветке. Соответственно, нет смысла рассматривать все позиции. Например, из позиции (10,3) 2-й игрок обязательно пойдет в (20,3), а не в (10,6), например.
Смотрим предыдущий ход. Чтобы 2-й игрок не выйграл, 1-й игрок на 1-м ходе не должен идти в позицию (10,3). Он может идти в остальные позиции. Запретная позиция для 1-го игрока перечеркнута красным:
Рассматривая дальнейшие ходы не будем ветвить позиции, которые идут из позиции (10,3). После 3-х ходов дерево будет выглядеть так:

Из рисунка видно, что любой ход 1-ого игрока на 3-м ходу будет выйгрышным. Поэтому, выигрывает 1-й игрок.
Представим решение также в виде таблицы (выйгрышные ходы выделены розовым):
1 ход | 2 ход | 3 ход | |
---|---|---|---|
Старт | 1-й игрок (выйгрышный ход) | 2-й игрок (все ходы) | 1-й игрок (выйгрышный ход (один из вариантов)) |
5,3 | 5,6 | 10,6 |
20,6 |
5,12 | 10,12 | ||
9,6 | 18,6 | ||
5,10 | 5,20 | ||
9,3 |
18,3 |
36,3 |
|
9,6 | 18,6 | ||
13,3 | 26,3 | ||
9,7 | 18,7 | ||
5,7 | 10,7 | 20,7 | |
5,14 | 10,14 | ||
9,7 | 18,7 | ||
5,11 | 5,22 |
Выигрывает 1-й игрок.
Он выигрывает своим 2-м ходом.