Розбір завдання C3 (демо ЄДІ 2009)

Два гравці грають у наступну гру. На координатній площині стоїть фішка. Гравці ходять по черзі. На початку гри фішка знаходиться у точці з координатами (5,2). Хід полягає в тому, що гравець переміщає фішку з точки з координатами (x, y) в одну з трьох точок: або точку з координатами (x +3, y), або в точку з координатами (x, y +3), або точку з координатами (x, y+4). Виграє гравець, після ходу якого відстань по прямій від фішки до точки з координатами (0,0) не менше ніж 13 одиниць. Хто виграє при безпомилковій грі обох гравців – гравець, який робить перший хід, або гравець, який робить другий хід? Яким повинен бути перший хід гравця, що виграє? Відповідь обґрунтуйте.

Щоб хтось із гравців виграв, він повинен потрапити до такої координати, де х 2 +у 2 =13 2 , тобто. х 2 + 2 >=169.

Зобразимо хід гри як дерева рішень. Після перших 2-х ходів воно виглядатиме так:

На дереві зображено всі можливі варіанти ходів. Одним кольором у рядку підкреслено однакові значення координат. По ходу гри розгалужуватимемо лише різні координати.

Коли перший гравець здійснює третій хід, він виграє, коли потрапляє в координати: 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.

Подаємо рішення також у вигляді таблиці (виграшні ходи виділені рожевим):