Олимпиадная задача Карасева: пересечение 100 множеств на прямой, классы 8-10
На прямой выбрано 100 множеств A1, A2, .. , A100, каждое из которых является объединением 100 попарно непересекающихся отрезков. Докажите, что пересечение множеств A1, A2, .. , 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.
Тогда
2k2m+2n-2
т.е.
k m+n-1.
Лемма доказана.
Теперь решим задачу: пересекая A1последовательно с A2, A3, A100, мы увидим, что количество отрезков в пересечении будет не более100+100-1=199,199+100-1=298,9802+100-1=9901, что и требовалось доказать.
Обсуждение
0Комментариев пока нет.