Разделы 
Дополнительно
Задача по математике - 3682
2019-06-15 
На прямой дано 50 отрезков. Докажите, что верно хотя бы одно из следующих утверждений:
а) некоторые восемь отрезков имеют общую точку; б) найдется восемь отрезков, никакие два из которых не имеют общей точки.
Решение:
Пусть $[a_1,b_1]$ - отрезок с наименьшим правым концом. Если число отрезков, содержащих точку $b_1$, больше 7, то задача решена. Если оно меньше или равно 7, то имеется по крайней мере 43 отрезка, лежащих целиком правее $[a_1, b_1]$. Выберем из них отрезок $[a_2, b_2]$ с наименьшим правым концом. Тогда либо $b_2$ принадлежит 8 отрезкам, либо имеется 36 отрезков, лежащих правее $b_2$. Продолжая это рассуждение, мы либо найдем точку, принадлежащую 8 отрезкам, либо получим 7 попарно не пересекающихся отрезков $[a_1, b_1], [a_2, b_2], \cdots, [a_7, b_7]$ таких, что правее $[a_k, b_k]$ лежит не меньше $50 - 7k$ отрезков, т. е. правее $[a_7, b_7]$ лежит еще по крайней мере один отрезок $[a_8, b_8]$.
Точно так же можно доказать, что из $mn + 1$ отрезков можно выбрать либо $m + 1$ попарно не пересекающихся отрезков, либо $n + 1$ отрезков, имеющих общую точку. Вот еще похожая задача: из любых $mn + 1$ натуральных чисел можно выбрать цепочку из $m + 1$ чисел, в которой каждое делится на предыдущее, либо $n + 1$ чисел, из которых ни одно не делится на другое. Это частные случаи общей теоремы Дилуорса: в частично упорядоченном множестве из $mn + 1$ элементов есть либо цепь из идущих в порядке возрастания элементов, либо $n + 1$ попарно несравнимых элементов.
Чтобы применить эту теорему к нашей задаче об отрезках, надо считать, что один отрезок «больше» другого, если он целиком лежит правее; тогда «попарно несравнимые» отрезки обязательно имеют общую точку (ею служит самый левый из их правых концов).
На прямой дано 50 отрезков. Докажите, что верно хотя бы одно из следующих утверждений:
а) некоторые восемь отрезков имеют общую точку; б) найдется восемь отрезков, никакие два из которых не имеют общей точки.
Решение:
Пусть $[a_1,b_1]$ - отрезок с наименьшим правым концом. Если число отрезков, содержащих точку $b_1$, больше 7, то задача решена. Если оно меньше или равно 7, то имеется по крайней мере 43 отрезка, лежащих целиком правее $[a_1, b_1]$. Выберем из них отрезок $[a_2, b_2]$ с наименьшим правым концом. Тогда либо $b_2$ принадлежит 8 отрезкам, либо имеется 36 отрезков, лежащих правее $b_2$. Продолжая это рассуждение, мы либо найдем точку, принадлежащую 8 отрезкам, либо получим 7 попарно не пересекающихся отрезков $[a_1, b_1], [a_2, b_2], \cdots, [a_7, b_7]$ таких, что правее $[a_k, b_k]$ лежит не меньше $50 - 7k$ отрезков, т. е. правее $[a_7, b_7]$ лежит еще по крайней мере один отрезок $[a_8, b_8]$.
Точно так же можно доказать, что из $mn + 1$ отрезков можно выбрать либо $m + 1$ попарно не пересекающихся отрезков, либо $n + 1$ отрезков, имеющих общую точку. Вот еще похожая задача: из любых $mn + 1$ натуральных чисел можно выбрать цепочку из $m + 1$ чисел, в которой каждое делится на предыдущее, либо $n + 1$ чисел, из которых ни одно не делится на другое. Это частные случаи общей теоремы Дилуорса: в частично упорядоченном множестве из $mn + 1$ элементов есть либо цепь из идущих в порядке возрастания элементов, либо $n + 1$ попарно несравнимых элементов.
Чтобы применить эту теорему к нашей задаче об отрезках, надо считать, что один отрезок «больше» другого, если он целиком лежит правее; тогда «попарно несравнимые» отрезки обязательно имеют общую точку (ею служит самый левый из их правых концов).
