Лист бумаги имеет форму круга. Можно ли провести на нем пять отрезков, каждый из которых соединяет две точки на границе листа так, чтобы среди частей, на которые эти отрезки делят лист, нашлись пятиугольник и два четырехугольника?

   Решение

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

Сложность: 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 диаметров, получаем требуемое. Второй случай очевиден.

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