Задача 58287

Тема:    [ Системы точек ]

Сложность: 5+ Классы: 8,9

Условие

На плоскости дано n3 точек. Пусть d — наибольшее расстояние между парами этих точек. Докажите, что имеется не более n пар точек, расстояние между которыми равно d.

Решение

Назовем диаметром отрезок длиной d, соединяющий пару данных точек. Концы всех диаметров, выходящих из точки A, лежат на окружности с центром A и радиусом d. Так как расстояние между любыми двумя точками не превосходит d, концы всех диаметров, выходящих из A, лежат на дуге, угловая величина которой не превосходит 60^o. Следовательно, если из точки A выходят три диаметра AB, AC и AD, то один из концов этих диаметров лежит внутри угла, образованного двумя другими. Пусть для определенности точка C лежит внутри угла BAD. Докажем, что тогда из точки C выходит не более одного диаметра. Предположим, что есть еще диаметр CP и точки B и P лежат по разные стороны от прямой AC (рис.). Тогда ABCP — выпуклый четырехугольник, поэтому AB + CP < AC + BP (см. задачу 9.14), т. е. d + d < d + BP, а значит, BP > d, чего не может быть.
В итоге получаем, что либо из каждой точки выходит не более двух диаметров, либо существует точка, из которой выходит не более одного диаметра. Теперь требуемое утверждение можно доказать индукцией по числу точек. Для n = 3 оно очевидно. Предположим, что утверждение доказано для любой системы из n точек, и докажем его для системы из n + 1 точки. В этой системе либо есть точка, из которой выходит не более одного диаметра, либо из каждой точки выходит не более двух диаметров. В первом случае отбрасываем эту точку и, воспользовавшись тем, что в оставшейся системе не более n диаметров, получаем требуемое. Второй случай очевиден.

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

книга
Автор	Прасолов В.В.
Год издания	2001
Название	Задачи по планиметрии
Издательство	МЦНМО
Издание	4*
глава
Номер	26
Название	Системы точек и отрезков. Примеры и контрпримеры
Тема	Системы точек и отрезков
параграф
Номер	1
Название	Системы точек
Тема	Системы точек
задача
Номер	26.004