Задача
На плоскости задано конечное множество точек. Доказать, что в нём найдётся точка, у которой имеется не более трёх ближайших к ней точек из этого же множества.
Решение
Предположим, что мы построили такое множествоMточек на плоскости, в котором у каждой не менее четырёх ближайших. Пустьr — наименьшее из расстояний между его точками. Рассмотрим множествоL⊂Mвсех точек, расстояние от которых до ближайших к ним равно r; в множествеL, очевидно, также у каждой точки будет не менее четырёх ближайших. Построим выпуклую оболочкуKмножестваL(наименьший выпуклый многоугольник, содержащийL). ПустьA — одна из крайних точекL, то есть одна из вершинK. ПустьB1,B2,B3,B4 — четыре точки изL, находящиеся на расстоянииrотA. Ясно, что любой из углов$\angle$BiABjне меньше 60o, потому что |BiBj| ≥r(i,j= 1, 2, 3, 4,i≠j). Это обстоятельство явно противоречит тому, что все точкиB1,B2,B3,B4лежат в одном угле с вершинойA, меньшем 180o. (Решение задачи M388 a) из журнала "Квант".)
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь