ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 66651
Тема:    [ Системы точек ]
Сложность: 3+
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Автор: Фольклор

На плоскости даны 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.

Источники и прецеденты использования

олимпиада
Название Олимпиада по геометрии имени И.Ф. Шарыгина
год
Год 2018
Заочный тур
задача
Номер 10 [8-9 кл]

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .