|
|
 |
Условие
На плоскости расположено N точек. Отметим середины всевозможных отрезков с
концами в этих точках. Какое наименьшее число отмеченных точек может
получиться?
Решение
Рассмотрим всевозможные расстояния между заданными N точками и выберем
среди этих расстояний наибольшее — пусть это расстояние между какими-то двумя точками A и B. Соединим точку A с остальными N − 1 точками; получим N − 1 отрезков. Середины этих отрезков различны и все лежат внутри или на границе круга с центром в точке A радиуса |AB|. Аналогично, соединив точку B с оставшимися N − 1 точками, получим N − 1 отмеченных точек (середин), расположенных внутри или на границе круга того же радиуса с центром в точке B.
Построенные два круга имеют только одну общую точку — середину отрезка AB. Следовательно, всегда имеется по крайней мере 2 ( N − 1 ) − 1 (так как середину отрезками мы учитываем дважды) отмеченных середин, то есть не менее (2N − 3) отмеченных точек.
Покажем, что 2N − 3 — это наименьшее число отмеченных точек. Пусть заданные N точек лежат на одной прямой, причём расстояния между соседними точками одинаковы. Легко видеть, что в этом случае число отмеченных точек — середин равно (N − 2) + N − 1 = 2N − 3. Тем самым всё доказано.
