Условие
На плоскости даны 2018 точек, все попарные расстояния между которыми различны. Для каждой точки отметили ближайшую к ней среди остальных. Какое наименьшее число точек может оказаться отмечено?
Решение
Разобьем точки на классы так, что для всех точек одного класса ближайшей является одна и та же точка. Заметим, что каждый класс содержит не больше пяти точек. Действительно, пусть точка $B$ – ближайшая к точкам $A_1, A_2, \dots, A_n$, перечисленным в порядке обхода вокруг $B$. Тогда $A_1A_2$ – наибольшая сторона в треугольнике $A_1A_2B$ и, значит, $\angle A_1BA_2 > 60^{\circ}$. Аналогичное верно для углов $A_2BA_3,\ldots, A_nBA_1$, поэтому $n\le 5$. Если $n=5$, то нетрудно видеть, что одна из точек $A_1, \dots, A_5$ (скажем, $A_1$) является ближайшей для $B$. Аналогичные рассуждения показывают, что класс точки $B$ содержит меньше пяти точек.
Следовательно, из $n$ точек отмечено будет не меньше, чем $2n/9$, т.е. при $n=2018$ не меньше $449$ точек.
С другой стороны, в изображенной на рисунке выше конфигурации из $9$ точек для пяти точек, отмеченных кружками, ближайшей будет точка $A$, а для четырех точек, отмеченных квадратиками, – точка $B$. Поэтому, если взять $224$ таких группы, расположенных далеко друг от друга, и добавить к одной из них две точки, для которых ближайшей будет точка $C$, то отмечено будет $223\cdot 2+3=449$ точек.
Ответ
449.
Источники и прецеденты использования
