На плоскости заданы $2n$ точек — $n$ синих и $n$ красных, причём никакие три точки не лежат на одной прямой. Докажите, что можно провести $n$ отрезков так, что у каждого отрезка один конец лежит в красной точке, другой — в синей точке, и никакие два отрезка не имеют общих точек.
Назовём системой всякие $n$ отрезков, таких, что у каждого отрезка один конец лежит в красной точке, другой — в синей точке, и никакие два отрезка не выходят из одной точки. Чтобы построить систему, надо как‑нибудь разбить наши $2n$ точек на $n$ пар — по одной красной и одной синей в каждой паре — и соединить точки каждой пары отрезком.
Надо найти систему, отрезки которой не имеют друг с другом общих точек. Докажем, что годится система, для которой сумма длин её отрезков — минимальная из всех возможных (для данных $2n$ точек). Действительно, пусть у нас есть такая система с минимальной суммой длин отрезков. Докажем, что все её отрезки не имеют общих точек. Допустим противное: пусть два её отрезка $K_1C_1$ и $K_2C_2$ имеют общую точку $O$ ($K_1$, $K_2$ — красные, $C_1$, $C_2$ — синие точки, рис. 1). Докажем, что тогда сумма длин отрезков этой системы может быть уменьшена.
По условию никакие три из точек $K_1$, $K_2$, $C_1$, $C_2$ не лежат на одной прямой. Тогда точки $K_1$, $K_2$, $C_1$, $C_2$ — вершины выпуклого четырёхугольника. Разумеется, сумма длин любых двух его противоположных сторон меньше суммы длин диагоналей, например, $|K_1C_2|+|K_2C_1|\lt|K_1C_1|+|K_2C_2|$ (см. рис. 1).
Заменив в нашей системе отрезки $K_1C_1$ и $K_2C_2$ отрезками $K_1C_2$ и $K_2C_1$, мы уменьшим сумму длин всех отрезков, что противоречит предположению.
Рис. 1Рис. 2
Приведём другое решение задачи, предложенное её автором С. Охитиным (Оренбург), а также несколькими читателями.
Докажем сначала такую лемму:
Для любого множества $n$ синих и $n$ красных точек, о котором говорится в условии, можно провести прямую $l$ так, что в каждой из полуплоскостей, на которые $l$ разбивает плоскость, лежит поровну синих и красных точек, причём не все $2n$ точек лежат в одной полуплоскости и никакая из них не принадлежит $l$.
Рассмотрим выпуклую оболочку множества из наших $2n$ точек: наименьший содержащий их выпуклый многоугольник. Несколько из этих $2n$ точек служат его вершинами. Разберём два случая.
а) Среди вершин есть и красные, и синие точки. В этом случае найдутся две соседние вершины разных цветов: $K_0$ и $C_0$. Проведём прямую $l$ параллельно отрезку $K_0C_0$ так, чтобы все остальные $2n-2$ точки лежали по другую сторону от $l$. Это и есть нужная прямая (рис. 2).
Рис. 3
б) Все вершины — одного цвета, скажем, синего. Выберем какое‑то направление так, чтобы никакая прямая этого направления не проходила через две точки нашего множества. Можно считать, что это направление — вертикальное (рис. 3). Будем двигать равномерно вертикальную прямую (слева направо) и отметим те моменты времени $t_1$, $\ldots$, $t_{2n}$, когда она будет проходить точки нашего множества. Обозначим через $f(t)$ разность между количеством синих и красных точек в левой полуплоскости нашей прямой в момент времени $t$. На каждом отрезке, на которые точки $t_1$, $t_2$, $\ldots$, $t_{2n}$ разбивают ось $-\infty\lt t\lt+\infty$, функция $t\to f(t)$ постоянна, в частности, $f(t)=1$ при $t_1 \lt t \lt t_2$ (слева от прямой — одна синяя точка и $0$ красных), $f(t)=-1$ при $t_{2n-1}\lt t\lt t_{2n}$, и при каждом переходе через $t_i$ значение $f(t)$ меняется на единицу. Ясно, что на каком‑то отрезке $(t_k,t_{k+1})$ значение $f(t)$ должно равняться 0.
Любую вертикальную прямую, соответствующую моменту времени $t$ между $t_k$ и $t_{k+1}$, можно взять в качестве $l$. Лемма доказана.
Теперь утверждение задачи легко доказать индукцией по $n$. Для $n=1$ (даны две точки — синяя и красная) оно очевидно. Предположим, что для всех множеств из $2k$ точек ($k$ синих и $k$ красных), где $k\lt n$, утверждение справедливо. Тогда оно справедливо и для множеств из $2n$ точек: пользуясь леммой, мы можем разбить такое множество на два, к каждому из которых применимо предположение индукции. Отрезки, лежащие в одной и другой полуплоскости, разумеется, не будут пересекаться.
