Задача 109738

Темы:    [ Системы отрезков, прямых и окружностей ] [ Объединение, пересечение и разность множеств ] [ Выпуклая оболочка и опорные прямые (плоскости) ]

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

Условие

Автор: Карасев Р.

На прямой выбрано 100 множеств A₁, A₂, .. , A100 , каждое из которых является объединением 100 попарно непересекающихся отрезков. Докажите, что пересечение множеств A₁, A₂, .. , A100 является объединением не более 9901 попарно непересекающихся отрезков (точка также считается отрезком).

Решение

Пусть множества A и B на прямой являются объединениями m и n отрезков соответственно. Тогда A B – объединение не более m+n-1 отрезков. Ясно, что A B – тоже объединение отрезков. Пусть их количество равно k . Концы отрезков A B являются концами отрезков A или B . Следовательно, рассматривая концы отрезков A B , получаем:

2k 2m+2n. (*)
Но при этом самый левый конец отрезка из всех концов A или B либо не принадлежит A B , либо входит и в концы A и в концы B . Значит, правую часть (*) можно уменьшить на 1. Аналогично, рассматривая самый правый конец A или B , мы уменьшаем правую часть (*) еще на 1. Тогда
2k 2m+2n-2
т.е.
k m+n-1.
Лемма доказана. Теперь решим задачу: пересекая A1 последовательно с A2 , A3 , A100 , мы увидим, что количество отрезков в пересечении будет не более 100+100-1=199 , 199+100-1=298 , 9802+100-1=9901 , что и требовалось доказать.

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

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	2001
Этап
Вариант	5
Класс
Класс	10
задача
Номер	01.5.10.2