Задача 8. Одна против всех

Условие на языке расстояний

Серединный перпендикуляр к отрезку $XY$ — это прямая из точек, одинаково удалённых от $X$ и от $Y$. Она делит плоскость на две половины: по одну сторону лежат все точки, которые ближе к $X$, чем к $Y$, по другую — те, которые ближе к $Y$ (рисунок ниже). Так что фраза «с одной стороны от перпендикуляра одна точка, с другой — $n-1$» означает вот что.

Для любых двух отмеченных точек $X$ и $Y$ одна из них «одинока»: все остальные $n-2$ отмеченные точки ближе к другой точке пары. Если одинока $Y$, то для каждой другой точки $Z$ верно $ZX < ZY$. А слова «на перпендикуляре точек нет» запрещают равенства: ни одна точка $Z$ не может быть одинаково удалена от $X$ и от $Y$.

При $n = 2$ условие выполнено само собой: по одной точке с каждой стороны. Нам нужно выяснить, насколько большим может быть $n$; будем доказывать, что $n \le 5$, поэтому дальше считаем, что точек хотя бы четыре.

Самый короткий отрезок

Среди всех отрезков с концами в отмеченных точках выберем самый короткий; назовём его $AB$. Возьмём любые две другие отмеченные точки $C$ и $D$ и проведём серединный перпендикуляр к $AC$.

Где относительно него лежит $B$? Расстояние $AB$ — самое маленькое из всех, поэтому $AB < BC$: равенства быть не может, иначе $B$ лежала бы на этом перпендикуляре. Значит, $B$ ближе к $A$, чем к $C$, и лежит на стороне $A$. Но тогда на стороне $A$ уже две точки — $A$ и $B$, — а по условию на одной из сторон ровно одна. Выходит, одинока $C$, и все остальные точки, в том числе $D$, лежат на стороне $A$: $AD < CD$ (рисунок ниже).

Точно так же серединный перпендикуляр к $AD$ показывает, что одинока $D$, поэтому $AC < CD$. А если повторить это с $B$ вместо $A$, получится $BC < CD$ и $BD < CD$.

Угол больше 60°

Если $A$, $C$, $D$ лежат на одной прямой, неравенства $CD>AC$ и $CD>AD$ означают, что $A$ лежит между $C$ и $D$. Тогда угол $CAD=180^\circ>60^\circ$.

В остальных случаях треугольник $ACD$ невырожденный. Мы выяснили: $AD < CD$ и $AC < CD$, то есть $CD$ — самая большая сторона. Против большей стороны лежит больший угол, поэтому угол $CAD$, лежащий против $CD$, — самый большой из трёх углов треугольника.

Если бы этот угол был не больше $60^\circ$, то и два других тоже, и сумма всех трёх была бы не больше $180^\circ$ — с равенством только когда все три угла ровно по $60^\circ$, то есть у равностороннего треугольника. Но у нас $CD > AD$, стороны не равны. Значит, $\angle CAD > 60^\circ$ (рисунок ниже).

Запомним: это верно для любых двух отмеченных точек $C$ и $D$, отличных от $A$ и $B$. Из точки $A$ любые две другие точки (кроме $B$) видны под углом больше $60^\circ$. То же самое верно и для точки $B$: $\angle CBD > 60^\circ$.

Все лучи из A — в одной полуплоскости

Теперь проведём серединный перпендикуляр к самому короткому отрезку $AB$. По условию одна из точек $A$, $B$ одинока; пусть это $A$ (иначе просто поменяем буквы местами — всё, что мы доказали, верно и для $A$, и для $B$). Тогда каждая другая отмеченная точка $X$ ближе к $B$, чем к $A$: $XB < XA$.

Серединный перпендикуляр к $AB$ параллелен прямой $\ell$, проведённой через $A$ перпендикулярно $AB$, и проходит между $A$ и $B$. Все точки $X$ лежат строго на стороне $B$ от серединного перпендикуляра. Значит, они тем более лежат на стороне $B$ от $\ell$: все лучи $AX$ уходят строго в одну полуплоскость. Это рассуждение верно и когда $X$, $A$, $B$ лежат на одной прямой.

Упорядочим эти $n-2$ лучей по повороту от одного края полуплоскости к другому. Между соседними лучами получается $n-3$ углов, и каждый из них больше $60^\circ$ по шагу 3. Все вместе они составляют угол между крайними лучами, а он меньше $180^\circ$: все лучи лежат строго внутри полуплоскости. Получаем $60^\circ \cdot (n-3) < 180^\circ$, то есть $n-3 < 3$ и $n \le 5$.

Пример для n = 5: крест

Оценка $n \le 5$ получена; осталось показать, что пять точек бывают. Возьмём крест: $A(0;\,0)$, $B(0;\,-1)$, $C(0;\,2)$, $D(-3;\,0)$, $E(4;\,0)$ — точки $B$ и $C$ на вертикали через $A$, точки $D$ и $E$ на горизонтали (рисунок ниже).

Сравнивать расстояния удобно через их квадраты: по теореме Пифагора квадрат расстояния между точками $(x_1;\,y_1)$ и $(x_2;\,y_2)$ равен $(x_1-x_2)^2+(y_1-y_2)^2$ — целое число, корни не нужны. Выпишем квадраты расстояний от каждой точки до остальных в порядке $A$, $B$, $C$, $D$, $E$:

• от $A$: до $B$ — $1$, до $C$ — $4$, до $D$ — $9$, до $E$ — $16$;
• от $B$: до $A$ — $1$, до $C$ — $9$, до $D$ — $10$, до $E$ — $17$;
• от $C$: до $A$ — $4$, до $B$ — $9$, до $D$ — $13$, до $E$ — $20$;
• от $D$: до $A$ — $9$, до $B$ — $10$, до $C$ — $13$, до $E$ — $49$;
• от $E$: до $A$ — $16$, до $B$ — $17$, до $C$ — $20$, до $D$ — $49$.

В каждой строке числа растут слева направо, и равных среди них нет. Проверим любую пару $X$, $Y$, где $X$ стоит в списке раньше $Y$. Для каждой другой точки $Z$ в её строке расстояние до $X$ стоит левее расстояния до $Y$, то есть $ZX < ZY$: точка $Z$ на стороне $X$. Значит, на стороне $X$ лежат $X$ и все три остальные точки — четыре, а $Y$ одна. И ни одна точка не попала на перпендикуляр, потому что равных расстояний в строках нет. Все десять пар подходят, $n = 5$ достигается.

Ответ: $5$.