Задача M301

Условие

** На плоскости заданы $2n$ точек — $n$ синих и $n$ красных, причем никакие три точки не лежат на одной прямой. Докажите, что можно провести $n$ отрезков так, что у каждого отрезка один конец лежит в красной точке, другой — в синей точке, и никакие два отрезка не имеют общих точек.

С. Охитин, ученик 10 класса (Оренбург)

Рис. 1.

Решение

На плоскости заданы 2n мочек — n синих и n красных, причем никакие три мочки не лежат на одной прямой. Доказите, что можно проверить n отрезков мак, что у каждой отрезка один конец лежит в красной мочке, другой — в синей мочке, и никакие два отрезка не имеют общих мочек.

Назовем системой вскрытие $n$ отрезков, таких, что у каждой отрезка один конец лежит в красной мочке, другой — в синей мочке, и никакие два отрезка не выходят из одной точки. Чтобы построить систему, надо как-нибудь разбить наши 2n точек на $n$ пар — по одной красной и одной синей в каждой паре — и соединить точки каждой пары отрезком.

Надо найти систему, отрезки которой не имеют друг с другой обших точек. Доказем, что годится система, для которой сумма длины отрезков — минимальная из всех возможных (для данных 2n точек). Действительно, пусть у нас есть такая система с минимальной суммой длины отрезка-

52

ков. Докажем, что все ее отрезки не имеют общих точек. Допустим противное: пусть два ее отрезка $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| < |K_1C_1| + |K_2C_2|$ (см. рис. 1).

Заменив в нашей системе отрезки $K_1C_1$ и $K_2C_2$ отрезками $K_1C_2$ и $K_2C_1$, мы уменьшим сумму длины отрезков, что противоречит предположению.

Приведем другое решение задачи, предложенное ее автором C. Охимным (Оренбург), а также несколькими читателями.

Докажем сначала такую лемму:

для любого множества $n$ синхии и $n$ красных точек, о котором говорится в условиям, можно проверить прямую $l$马克, что в каждой из полуплоскостей, на котором лазьваем плоскость, лежит поровну синхии и красных точек, причем не все $2n$ точек лежат в одной полуплоскости и нижкая из них не принадлежит $l$.

Рассмотрим выпуклую оболочку множества из наших $2n$ точек: наименьший содержащий их выпуклый многоугольник. Несколько из этих $2n$ точек служат его вершинами. Разберем два случая.

a) Среди вершин есть и красные, и синные точки. В этом случае найдет две соседние вершины разных цветов: $K_0$ и $C_0$. Проведем прямую $l$ параллельно отрезку $K_0C_0$ так, чтобы все остальные $2n-2$ точки лежали по другую сторону от $l$. Это и есть нужная прямая (рис. 2).

b) Все вершины — одного цвета, скажем, синero. Выберем какое-то направление так, чтобы никакая прямая этого направления не проходила через точки нашего множества. Можно считать, что это направление — вертикальное (рис. 3). Будем dvгать равномерно вертикальное прямую (слева направо) и отметим те моменты времени $t_1, \dots, t_{2n}$, когда она будет проходить точки нашего множества. Обозначим через $f(t)$ разность между количеством синхии и красных точек влевой полуплоскости нашей прямой в момент времени $t$. На каждом отрезке, на которых точки $t_1, t_2, \dots, t_{2n}$ разбиются ось $-\infty < t < +\infty$, функция $t \rightarrow f(t)$ построена, в частиности, $f(t) = 1$ при $t_1 < t < t_2$ (слева от прямой — одна синяя точка и 0 красных), $f(t) = -1$ при $t_{2n-1} < t < t_{2n}$, и при каждом перехождение через $f(t)$ меняется на ед и ни цу. Ясно, что на каком-то отрезке $]t_h, t_{h+1}$ значение $f(t)$ должно равняться 0.

Любую вертикальную прямую, соответствующую моменту времени $t$ между $t_h$ и $t_{h+1}$, можно взять в качестве $l$. Лемма доказана.

Теперь утверждение задачи легко доказать индукцией по $n$. Для $n = 1$ (данные точки — синяя и красная) оно очевидно. Предположим, что для всех множества из $2k$ точек ($k$ синих и $k$ красных), где $k < n$, утверждение справедливо. Тогда оно справедливо и для множества из $2n$ точек: пользоваться леммой, мы можем разбить такое множество на два, к каждому из которых применимо предположение индукции. Отрезки, лежащие в одной и другой полуплоскости, разумеется, не будут пересекаться.

A. Л. Тоом, Н. Б. Васильев

53