Разделы 
Дополнительно
Задача по математике - 2065
2019-01-23 
В клетчатом прямоугольнике $49 \times 69$ отмечены все $50 \cdot 70$ вершин клеток. Двое играют в следующую игру: каждым своим ходом каждый игрок соединяет две точки отрезком, при этом одна точка не может являться концом двух проведенных отрезков. Отрезки могут содержать общие точки. Отрезки проводятся до тех пор, пока точки не кончатся. Если после этого первый может выбрать на всех проведенных отрезках направления так, что сумма всех полученных векторов равна нулевому вектору, то он выигрывает, иначе выигрывает второй. Кто выигрывает при правильной игре?
Решение:
Первое решение. Разобьем все отмеченные точки на пары так, что любой отрезок с концами в точках одной пары - горизонтальный отрезок длины 1. Опишем выигрышную стратегию первого игрока. Пусть первым ходом он соединит точки из какой-нибудь пары. Далее, если второй соединяет отрезком две точки какой-нибудь пары, то первый соединяет отрезком две точки другой пары (назовем эти два проведенных отрезка двойкой первого типа). Если же второй соединяет отрезком две точки из разных пар, то первый соединяет отрезком две оставшиеся точки из этих пар (назовем такие два отрезка двойкой второго типа). Заметим, что количество точек делится на 4, поэтому последний ход сделает второй. Первый будет делать ответные ходы до тех пор, пока не останется одна пара - эти две оставшиеся точки соединит отрезком второй игрок. Теперь заметим, что в двойке первого типа можно выбрать направления так, чтобы сумма двух векторов равнялась нулевому вектору, а двойке второго типа можно выбрать направления так, чтобы сумма двух векторов равнялась горизонтальному вектору длины 2 (любого из двух направлений). Теперь первому нужно так выбрать направления в двойках второго типа, чтобы суммарная длина всех векторов в этих двойках равнялась либо нулевому вектору, либо горизонтальному вектору длины 2. После этого останется только два отрезка длины 1 (первый ход первого игрока и последний ход второго), на которых первому игроку нужно выбрать направления так, чтобы сумма всех векторов равнялась нулевому вектору.
Второе решение. Будем считать, что большая сторона прямоугольника параллельна оси $O_x$, а меньшая - $O_y$, при этом левый нижний угол прямоугольника совпадает с началом координат.
Лемма 1. Пусть игроки провели все отрезки. Тогда, независимо от расстановки стрелок, проекция вектора суммы на каждую из осей будет иметь четную длину.
Доказательство. Рассмотрим проекцию вектора суммы на ось $O_x$. Для каждой точки в зависимости от направления вектора ее координата по оси $O_x$ берется либо со знаком плюс, либо со знаком минус. Сумма координат (с соответствующими знаками) по оси $O_x$ всех точек прямоугольника и даст проекцию вектора суммы на ось $O_x$. Однако пятьдесят из этих точек имеют координату $0$, пятьдесят имеют координату $1, \cdots$, пятьдесят имеют координату 69. То есть среди этих чисел четное количество нечетных. Это и означает, что соответствующая сумма будет четной. Аналогично проекция вектора суммы на ось $O_y$ будет иметь четную длину. Лемма доказана.
Лемма 2. Пусть имеется набор отрезков с концами в целочисленных точках прямоугольника $49 \times 69$. Тогда можно так выбрать направления на этих отрезках, что проекция вектора суммы на ось $O_x$ будет меньше 140, а на ось $O_y$ - меньше 100.
Доказательство. Разобьем отрезки набора на четыре группы: параллельных оси $O_x$ (группа $A$), параллельных оси $O_y$ (группа $B$), тех, у которых правый конец выше левого (группа $C$), и тех, у которых правый конец ниже левого (группа $D$). Заметим, что если взять два отрезка из одной группы, то на них так можно выбрать направления, что по модулю координаты вектора их суммы будут не больше 69 по оси $O_x$ и не более 49 по оси $O_y$ (назовем такой вектор коротким). Также заметим, что если у набора векторов все направления поменять на противоположные, то вектор суммы изменит лишь знак.
Будем теперь проводить следующую процедуру. На каждом шаге будем выбирать пару отрезков из одной группы и заменять их соответствующим отрезком, который соответствует короткому вектору (новый отрезок может попасть в другую группу). Если в процессе получится отрезок нулевой длины, выкинем его. Заметим тогда, что если в полученном наборе мы можем расставить направления требуемым образом, то и в старом это было возможно.
Через некоторое число шагов мы придем к такой ситуации, что в каждой группе будет не более одного отрезка. Выбрав направления на отрезках из групп $C$ и $D$, мы получим вектор, проекция которого на ось $O_x$ будет меньше 140, а на ось $O_y$ - меньше 100. Пусть обе его координаты неотрицательны. Если теперь на отрезках из групп $A$ и $B$ выбрать отрицательные направления, то у итогового вектора суммы проекция на ось $O_x$ будет меньше 140, а на ось $O_y$ - меньше 100.
Лемма доказана.
Перейдем к решению задачи. Опишем стратегию первого игрока. Ему необходимо будет провести 140 горизонтальных отрезков длины 1 и 100 вертикальных отрезков длины 1 (назовем их красными). Тогда, после того как будут проведены все отрезки, на всех не красных отрезках по лемме 2 он так может выбрать направления, что проекция вектора суммы на ось $O_x$ будет меньше 140, а на $O_y$ - меньше 100. Теперь ему останется выбрать направления на красных отрезках так, чтобы проекция вектора суммы на каждую из осей будет равна нулю. Поскольку по лемме 1 проекция вектора суммы на каждую из осей будет иметь четную длину, он сможет это сделать и выиграет.
Покажем, как первому игроку провести требуемое количество красных отрезков. Выделим $25 \cdot 35 = 875$ квадратиков, каждый из которых содержит четыре отрезка длины 1 (см. рис.). Каждым своим ходом первый будет отмечать вертикальный или горизонтальный отрезок в одном из квадратиков. Для этого ему потребуется 240 ходов, каждым из которых первый тратит один квадратик. Заметим, что второй каждым своим ходом «портит» не более двух квадратиков. Таким образом, после каждого хода первого и второго используется не более трех квадратиков. Поскольку $240 \cdot 3 = 720 < 875$, первый сможет провести 240 красных отрезков нужных направлений, что и требовалось.
Ответ. Выигрывает первый.
В клетчатом прямоугольнике $49 \times 69$ отмечены все $50 \cdot 70$ вершин клеток. Двое играют в следующую игру: каждым своим ходом каждый игрок соединяет две точки отрезком, при этом одна точка не может являться концом двух проведенных отрезков. Отрезки могут содержать общие точки. Отрезки проводятся до тех пор, пока точки не кончатся. Если после этого первый может выбрать на всех проведенных отрезках направления так, что сумма всех полученных векторов равна нулевому вектору, то он выигрывает, иначе выигрывает второй. Кто выигрывает при правильной игре?
Решение:
Первое решение. Разобьем все отмеченные точки на пары так, что любой отрезок с концами в точках одной пары - горизонтальный отрезок длины 1. Опишем выигрышную стратегию первого игрока. Пусть первым ходом он соединит точки из какой-нибудь пары. Далее, если второй соединяет отрезком две точки какой-нибудь пары, то первый соединяет отрезком две точки другой пары (назовем эти два проведенных отрезка двойкой первого типа). Если же второй соединяет отрезком две точки из разных пар, то первый соединяет отрезком две оставшиеся точки из этих пар (назовем такие два отрезка двойкой второго типа). Заметим, что количество точек делится на 4, поэтому последний ход сделает второй. Первый будет делать ответные ходы до тех пор, пока не останется одна пара - эти две оставшиеся точки соединит отрезком второй игрок. Теперь заметим, что в двойке первого типа можно выбрать направления так, чтобы сумма двух векторов равнялась нулевому вектору, а двойке второго типа можно выбрать направления так, чтобы сумма двух векторов равнялась горизонтальному вектору длины 2 (любого из двух направлений). Теперь первому нужно так выбрать направления в двойках второго типа, чтобы суммарная длина всех векторов в этих двойках равнялась либо нулевому вектору, либо горизонтальному вектору длины 2. После этого останется только два отрезка длины 1 (первый ход первого игрока и последний ход второго), на которых первому игроку нужно выбрать направления так, чтобы сумма всех векторов равнялась нулевому вектору.
Второе решение. Будем считать, что большая сторона прямоугольника параллельна оси $O_x$, а меньшая - $O_y$, при этом левый нижний угол прямоугольника совпадает с началом координат.
Лемма 1. Пусть игроки провели все отрезки. Тогда, независимо от расстановки стрелок, проекция вектора суммы на каждую из осей будет иметь четную длину.
Доказательство. Рассмотрим проекцию вектора суммы на ось $O_x$. Для каждой точки в зависимости от направления вектора ее координата по оси $O_x$ берется либо со знаком плюс, либо со знаком минус. Сумма координат (с соответствующими знаками) по оси $O_x$ всех точек прямоугольника и даст проекцию вектора суммы на ось $O_x$. Однако пятьдесят из этих точек имеют координату $0$, пятьдесят имеют координату $1, \cdots$, пятьдесят имеют координату 69. То есть среди этих чисел четное количество нечетных. Это и означает, что соответствующая сумма будет четной. Аналогично проекция вектора суммы на ось $O_y$ будет иметь четную длину. Лемма доказана.
Лемма 2. Пусть имеется набор отрезков с концами в целочисленных точках прямоугольника $49 \times 69$. Тогда можно так выбрать направления на этих отрезках, что проекция вектора суммы на ось $O_x$ будет меньше 140, а на ось $O_y$ - меньше 100.
Доказательство. Разобьем отрезки набора на четыре группы: параллельных оси $O_x$ (группа $A$), параллельных оси $O_y$ (группа $B$), тех, у которых правый конец выше левого (группа $C$), и тех, у которых правый конец ниже левого (группа $D$). Заметим, что если взять два отрезка из одной группы, то на них так можно выбрать направления, что по модулю координаты вектора их суммы будут не больше 69 по оси $O_x$ и не более 49 по оси $O_y$ (назовем такой вектор коротким). Также заметим, что если у набора векторов все направления поменять на противоположные, то вектор суммы изменит лишь знак.
Будем теперь проводить следующую процедуру. На каждом шаге будем выбирать пару отрезков из одной группы и заменять их соответствующим отрезком, который соответствует короткому вектору (новый отрезок может попасть в другую группу). Если в процессе получится отрезок нулевой длины, выкинем его. Заметим тогда, что если в полученном наборе мы можем расставить направления требуемым образом, то и в старом это было возможно.
Через некоторое число шагов мы придем к такой ситуации, что в каждой группе будет не более одного отрезка. Выбрав направления на отрезках из групп $C$ и $D$, мы получим вектор, проекция которого на ось $O_x$ будет меньше 140, а на ось $O_y$ - меньше 100. Пусть обе его координаты неотрицательны. Если теперь на отрезках из групп $A$ и $B$ выбрать отрицательные направления, то у итогового вектора суммы проекция на ось $O_x$ будет меньше 140, а на ось $O_y$ - меньше 100.
Лемма доказана.
Перейдем к решению задачи. Опишем стратегию первого игрока. Ему необходимо будет провести 140 горизонтальных отрезков длины 1 и 100 вертикальных отрезков длины 1 (назовем их красными). Тогда, после того как будут проведены все отрезки, на всех не красных отрезках по лемме 2 он так может выбрать направления, что проекция вектора суммы на ось $O_x$ будет меньше 140, а на $O_y$ - меньше 100. Теперь ему останется выбрать направления на красных отрезках так, чтобы проекция вектора суммы на каждую из осей будет равна нулю. Поскольку по лемме 1 проекция вектора суммы на каждую из осей будет иметь четную длину, он сможет это сделать и выиграет.
Покажем, как первому игроку провести требуемое количество красных отрезков. Выделим $25 \cdot 35 = 875$ квадратиков, каждый из которых содержит четыре отрезка длины 1 (см. рис.). Каждым своим ходом первый будет отмечать вертикальный или горизонтальный отрезок в одном из квадратиков. Для этого ему потребуется 240 ходов, каждым из которых первый тратит один квадратик. Заметим, что второй каждым своим ходом «портит» не более двух квадратиков. Таким образом, после каждого хода первого и второго используется не более трех квадратиков. Поскольку $240 \cdot 3 = 720 < 875$, первый сможет провести 240 красных отрезков нужных направлений, что и требовалось.
Ответ. Выигрывает первый.
