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