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