Разбор задачи C3 (демо ЕГЭ 2010)
Два игрока играют в следующую игру. На координатной плоскости стоит фишка. В начале игры фишка находится в точке с координатами (–2,–1). Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: (x+3,y), (x,y+4), (x+2,y+2). Игра заканчивается, как только расстояние от фишки до начала координат превысит число 9. Выигрывает игрок, который сделал последний ход. Кто выигрывает при безошибочной игре – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Чтобы кто-то из игроков выйграл,он должен попасть в такую координату, где х2+у2>92, т.е. х2+у2>81.
Изобразим ход игры в виде дерева решений. После первых 2-х ходов оно будет выглядеть так:
На дереве изображены все возможные варианты ходов. Одним цветом в строке подчертнуты одинаковые значения координат. По ходу игры будем ветвить только разные координаты.
Когда 1-й игрок совершает 3-й ход, он выигрывает, когда попадает в координату: -2,11, т.к. сумма квадратов х и у в этих случаях больше 81. На рисунке выйгрышные позиции 1-го игрока выделены сплошной рамкой:
Смотрим предыдущий ход. Чтобы 1-й игрок не выйграл, 2-й игрок на 2-м ходе не должен идти в позицию -2,7. Он может идти в остальные позиции. Запретная позиция для 2-го игрока перечеркнута красным:
Рассматривая дальнейшие ходы не будем ветвить позиции, которые идут из позиции -2,7.Когда 2-й игрок совершает 4-й ход, он выигрывает, когда попадает в координаты: 10,-1, 9,1, 1,11, 3,9, 2,11, 4,9, 6,7, т.к. сумма квадратов х и у в этих случаях больше 81. На рисунке выйгрышные позиции 2-го игрока на 4-м ходу выделены сплошной рамкой:
Смотрим предыдущий ход. Чтобы 2-й игрок не выйграл, 1-й игрок на 3-м ходе не должен идти в позиции: 7,-1, 6,1, 1,7, 3,5, 2,7, 4,5. Он может идти в остальные позиции: 4,3 и 5,3. На рисунке ниже они выделены пунктирной рамкой. Запретные позиции для 1-го игрока перечеркнуты красным.
Будем ветвить только позиции, идущие из позиций 4,3 и 5,3:
Из рисунка видно, что любой ход 1-ого игрока на 5-м ходу будет выйгрышным. Поэтому,выигрывает 1-й игрок.
Теперь необходимо найти выйгрышные ходы игрока на 3-м ходу (пойдем с конца дерева решений в начало). Это позиции 4,3 и 5,3 3-го хода. На рисунке выше они выделены пунктирной рамкой. Как бы не пошел 2-й игрок на 2-м ходу, у 1-го игрока есть выйгрышные ходы 4,3 и 5,3.
Необходимо определить выйгрышный ход 1-го игрока на 1-м ходу. Если он пойдет в позицию -1,1, то как бы не пошел на следующий ход 2-й игрок, у 1-го есть возможность попасть в выйгрышную позицию 4,3 или 5,3. Если 1-й игрок пойдет в позицию -2,3 или 0,1, 2-й игрок может пойти в позицию 0,5 на 3-м ходу, и тогда 1-й игрок не сможет сделать выйгрышный ход. На рисунке розовым выделен ход 2-го игрока в позицию 0,5, из которого нет выйгрышных ходов 4,3 и 5,3 для 1-го игрока:
Представим решение также в виде таблицы (выйгрышные ходы выделены розовым):
| 1 ход | 2ход | 3 ход | 4 ход | 5 ход | |
|---|---|---|---|---|---|
| Старт | 1-й игрок (выйгрышный ход) | 2-й игрок (все ходы) | 1-й игрок (выйгрышный ход) | 2-й игрок (все ходы) | 1-й игрок (выйгрышный ход) |
| -2,-1 | 1,-1 | 4,-1 | 4,3 | 7,3 | 10,3, 7,7, 9,5 |
| 4,7 | 7,7, 4,11, 6,9 | ||||
| 6,5 | 9,5, 6,9, 8,7 | ||||
| 1,3 | 4,3 | те же ходы, что описаны выше | |||
| 3,1 | 5,3 | 8,3 | 11,3, 8,7, 10,6 | ||
| 5,7 | 8,7, 5,11, 7,9 | ||||
| 7,5 | 10,5, 7,9, 9,7 | ||||
Выигрывает 1-й игрок. Его 1-й ход- поставить фишку в точку с координатами (-1,1).