Разделы 
Дополнительно
Задача по математике - 1953
2019-01-22 
На прямой выбрано 100 множеств $A_1,A_2,\cdots ,A_{100}$, каждое из которых является объединением 100 попарно непересекающихся отрезков. Докажите, что пересечение множеств $A_1,A_2,\cdots,A_{100}$ является объединением не более 9901 попарно непересекающихся отрезков (точка также считается отрезком).
Решение:
Лемма. Пусть множества $А$ и $В$ на прямой являются объединениями $m$ и $n$ отрезков соответственно. Тогда $А \cap В$ - объединение не более $m + n - 1$ отрезков.
Доказательство. Ясно, что $А \cap В$ - тоже объединение отрезков. Пусть их количество равно $к$. Концы отрезков $А \cap В$ являются концами отрезков $А$ или $В$. Следовательно, рассматривая концы отрезков $А \cap В$, получаем:
$2k \leq 2m + 2n$. (*)
Но при этом самый левый конец отрезка из всех концов $А$ или $В$ либо не принадлежит $А \cap В$, либо входит и в концы $А$ и в концы $В$. Значит, правую часть (*) можно уменьшить на 1. Аналогично, рассматривая самый правый конец $А$ или $В$, мы уменьшаем правую часть (*) еще на 1. Тогда $2k \leq 2m + 2n - 2$ т. е. лемма доказана.
Теперь решим задачу: пересекая $А_1$ последовательно с $А_2, А_3, \cdots, А_{100}$, мы увидим, что количество отрезков в пересечении будет не более $100 + 100 - 1 = 199, 199 + 100 - 1 = 298, \cdots, 9802 + 100 - 1 = 9901$, что и требовалось доказать.
На прямой выбрано 100 множеств $A_1,A_2,\cdots ,A_{100}$, каждое из которых является объединением 100 попарно непересекающихся отрезков. Докажите, что пересечение множеств $A_1,A_2,\cdots,A_{100}$ является объединением не более 9901 попарно непересекающихся отрезков (точка также считается отрезком).
Решение:
Лемма. Пусть множества $А$ и $В$ на прямой являются объединениями $m$ и $n$ отрезков соответственно. Тогда $А \cap В$ - объединение не более $m + n - 1$ отрезков.
Доказательство. Ясно, что $А \cap В$ - тоже объединение отрезков. Пусть их количество равно $к$. Концы отрезков $А \cap В$ являются концами отрезков $А$ или $В$. Следовательно, рассматривая концы отрезков $А \cap В$, получаем:
$2k \leq 2m + 2n$. (*)
Но при этом самый левый конец отрезка из всех концов $А$ или $В$ либо не принадлежит $А \cap В$, либо входит и в концы $А$ и в концы $В$. Значит, правую часть (*) можно уменьшить на 1. Аналогично, рассматривая самый правый конец $А$ или $В$, мы уменьшаем правую часть (*) еще на 1. Тогда $2k \leq 2m + 2n - 2$ т. е. лемма доказана.
Теперь решим задачу: пересекая $А_1$ последовательно с $А_2, А_3, \cdots, А_{100}$, мы увидим, что количество отрезков в пересечении будет не более $100 + 100 - 1 = 199, 199 + 100 - 1 = 298, \cdots, 9802 + 100 - 1 = 9901$, что и требовалось доказать.
