Республиканская олимпиада по математике, 2016 год, 11 класс


На плоскости выбраны 101 синяя и 101 красная точка, причем никакие три не лежат на одной прямой. Сумма попарных расстояний между красными точками равна 1 (то есть сумма длин отрезков с концами в красных точках), сумма попарных расстояний между синими тоже равна 1, а сумма длин отрезков с концами разных цветов равна 400. Докажите, что можно провести прямую, отделяющую все красные точки от всех синих. ( Ким А. )
посмотреть в олимпиаде

Комментарий/решение:

Комментарии от администратора Комментарии от администратора №1.     Назовем отрезок $\textit{красным}$, если он соединяет две красные точки, и $\textit{синим}$, если он соединяет две синие точки. А если отрезок соединяет две точки разных цветов, то такой отрезок назовем $\textit{обычным}$. Рассмотрим любые две точки красного цвета $A$ и $B$, и остальные красные точки ${{X}_{1}}$, ${{X}_{2}}$, $\ldots $, ${{X}_{99}}$. Тогда из условия задачи и неравенства треугольника имеем: \[1>\sum\limits_{i=1}^{99}{\left( A{{X}_{i}}+B{{X}_{i}} \right)}+AB>99AB+AB=100AB\Rightarrow \frac{1}{100}>AB.\] Следовательно, любой красный отрезок по длине меньше $\frac{1}{100}$. Аналогично, любой синий отрезок меньше $\frac{1}{100}$. Далее, без доказательства будем пользоваться тем фактом, что если на отрезке $PQ$ лежит точка $R$, а $S$ любая точка, то $RS \leq \max (SP,SQ)$.

Докажем, что никакой красный отрезок не пересекается ни с каким синим отрезком. От противного. Пусть красный отрезок ${{K}_{1}}{{K}_{2}}$ и синий отрезок ${{C}_{1}}{{C}_{2}}$ пересеклись в точке $O$. Тогда для любой красной точки $K$ и синей точки $C$ верны неравенства $$CK\le OC+OK\le \max \left( C{{C}_{1}},C{{C}_{2}} \right)+\max \left( K{{K}_{1}},K{{K}_{2}} \right)<\frac{1}{100}+\frac{1}{100}=\frac{2}{100}.$$ Следовательно, длина любого обычного отрезка меньше $\frac{2}{100}$. Количество таких отрезков ровно $101\cdot 101$. Тогда сумма длин обычных отрезков не больше $101\cdot 101\cdot \frac{2}{100}$, а по условию задачи эта сумма равна $400$. Противоречие.
Рассмотрим теперь выпуклую оболочку красных и синих точек. Тогда эти оболочки не пересекаются. Тогда очевидно, что можно провести прямую, для которой выпуклые оболочки будут лежать по разные стороны от этой прямой.
Замечание. Выпуклой оболочкой множества точек называется пересечение всех выпуклых множеств, содержащих все заданные точки.