ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 34991
Темы:    [ Принцип крайнего (прочее) ]
[ Принцип Дирихле (прочее) ]
[ Системы отрезков, прямых и окружностей ]
Сложность: 4-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

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


Подсказка

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


Решение

Пусть  [a1, b1]  – отрезок с наименьшим правым концом. Если число отрезков, содержащих точку b1, больше 7, то задача решена. Если оно не больше 7, то имеется по крайней мере  50 – 7 = 43  отрезка, лежащих целиком правее точки b1. Выберем из них отрезок  [a2, b2]  с наименьшим правым концом. Тогда либо b2 принадлежит восьми отрезкам, либо имеется  50 – 2·7 = 36  отрезков, лежащих целиком правее точки b2. Продолжая так и далее, мы либо найдём точку, принадлежащую восьми отрезкам, либо получим семь таких попарно не пересекающихся отрезков  [a1, b1],  [a2, b2],  ...,  [a7, b7],  что правее bk лежит еще  50 – 7k  отрезков, т.е. правее b7 лежит еще один отрезок  [a8, b8],  т.е. имеется восемь попарно не пересекающихся отрезков  [a1, b1],  [a2, b2],  ...,  [a8, b8].

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

web-сайт
задача

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .