Задача 34991

Темы:    [ Принцип крайнего (прочее) ] [ Принцип Дирихле (прочее) ] [ Системы отрезков, прямых и окружностей ]

Сложность: 4- Классы: 8,9,10

Условие

На прямой дано 50 отрезков.
Докажите, что либо некоторые восемь отрезков имеют общую точку, либо найдутся восемь отрезков, никакие два из которых не имеют общей точки.

Подсказка

Выбирайте отрезок с наименьшим правым концом, далее – отрезок с наименьшим правым концом из отрезков, не пересекающихся с первым отрезком, и т.д.

Решение

Пусть  [a₁, b₁]  – отрезок с наименьшим правым концом. Если число отрезков, содержащих точку b₁, больше 7, то задача решена. Если оно не больше 7, то имеется по крайней мере  50 – 7 = 43  отрезка, лежащих целиком правее точки b₁. Выберем из них отрезок  [a₂, b₂]  с наименьшим правым концом. Тогда либо b₂ принадлежит восьми отрезкам, либо имеется  50 – 2·7 = 36  отрезков, лежащих целиком правее точки b₂. Продолжая так и далее, мы либо найдём точку, принадлежащую восьми отрезкам, либо получим семь таких попарно не пересекающихся отрезков  [a₁, b₁],  [a₂, b₂],  ...,  [a₇, b₇],  что правее b_k лежит еще  50 – 7k  отрезков, т.е. правее b₇ лежит еще один отрезок  [a₈, b₈],  т.е. имеется восемь попарно не пересекающихся отрезков  [a₁, b₁],  [a₂, b₂],  ...,  [a₈, b₈].

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

web-сайт

задача