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