Задача 109840
|
|
 |
Условие
В клетчатом прямоугольнике 49×69 отмечены все 50· 70 вершин клеток. Двое играют в следующую игру: каждым своим ходом каждый игрок соединяет две точки отрезком, при этом одна точка не может являться концом двух проведенных отрезков. Отрезки могут содержать общие точки. Отрезки проводятся до тех пор, пока точки не кончатся. Если после этого первый может выбрать на всех проведенных отрезках направления так, что сумма всех полученных векторов равна нулевому вектору, то он выигрывает, иначе выигрывает второй. Кто выигрывает при правильной игре?Решение
Первое решение. Разобьем все отмеченные точки на пары так, что любой отрезок с концами в точках одной пары – горизонтальный отрезок длины 1.
Опишем выигрышную стратегию первого игрока.
Пусть первым ходом он соединит точки из какой-нибудь пары.
Далее, если второй соединяет отрезком две точки какой-нибудь пары, то первый соединяет отрезком две точки другой пары (назовем эти два проведенных отрезка двойкой первого типа).
Если же второй соединяет отрезком две точки из разных пар, то первый соединяет отрезком две оставшиеся точки из этих пар (назовем такие два отрезка двойкой второго типа).
Заметим, что количество точек делится на 4, поэтому последний ход сделает второй. Первый будет делать ответные ходы до тех пор, пока не останется одна пара – эти две оставшиеся точки соединит отрезком второй игрок.
Теперь заметим, что в двойке первого типа можно выбрать направления так, чтобы сумма двух векторов равнялась нулевому вектору, а двойке второго типа можно выбрать направления так, чтобы сумма двух векторов равнялась горизонтальному вектору длины 2 (любого из двух направлений).
Теперь первому нужно так выбрать направления в двойках второго типа, чтобы суммарная длина всех векторов в этих двойках равнялась либо нулевому вектору, либо горизонтальному вектору длины 2. После этого останется только два отрезка длины 1 (первый ход первого игрока и последний ход второго), на которых первому игроку нужно выбрать направления так, чтобы сумма всех векторов равнялась нулевому вектору.
Второе решение. Будем считать, что большая сторона прямоугольника параллельна оси Ox , а меньшая – Oy , при этом левый нижний угол прямоугольника совпадает с началом координат. Лемма 1.
