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