Олимпиадная задача Агеханова по геометрии и алгоритмам, 9

Олимпиадная задача Агеханова по комбинаторной геометрии для 9–11 классов

Задача

На плоскости даны n>1точек. Двое по очереди соединяют еще не соединенную пару точек вектором одного из двух возможных направлений. Если после очередного хода какого-то игрока сумма всех нарисованных векторов нулевая, то выигрывает второй; если же очередной ход невозможен, а нулевой суммы не было, то выигрывает первый. Кто выигрывает при правильной игре?

Решение

Выигрывает первый. Покажем, что первому игроку достаточно каждым ходом проводить вектор с максимальной абсциссой, а из всех векторов, имеющих абсциссу, равную максимальной, вектор с максимальной ординатой.

Действительно, докажем, что тогда сумма всех проведенных векторов будет иметь либо положительную абсциссу, либо нулевую абсциссу и положительную ординату (назовем такой вектор положительным). Очевидно, что каждым своим ходом первый игрок проводит положительный вектор, и сумма двух положительных векторов положительна. Также очевидно, что сумма векторов, проведенных за ход первым и вторым, положительна или ноль. Поэтому достаточно доказать, что после первого хода второго игрока эта сумма будет положительна (т.е. не будет нулевой). Пусть она нулевая, первый провел вектор , а второй – . Если абсциссы точек A и D не равны, то один из векторов и имеет абсциссу, большую, чем у (сумма этих абсцисс равна удвоенной абсциссе ), что невозможно. Если абсциссы A и D совпадают, то не совпадают ординаты (иначе A=D , B=C ); тогда абсциссы векторов , и равны, но у какого-то из первых двух векторов ордината больше, чем у третьего, что опять-таки невозможно.