|
|
 |
Условие
На прямой дано 50 отрезков. Докажите, что верно хотя бы одно из следующих утверждений:- некоторые 8 из этих отрезков имеют общую точку;
- некоторые 8 из этих отрезков таковы, что никакие два из них не пересекаются.
Решение
Вероятно, можно привести много различных теорем, частным случаем или следствием которых является утверждение этой задачи. Мы здесь укажем только одну из них.
Теорема. Пусть на прямой задана произвольная система отрезков.
Обозначим через M наименьшее количество точек на прямой таких, что
каждый из отрезков системы содержит одну из этих точек; через m –
наибольшее количество попарно непересекающихся отрезков, которые можно
выбрать из нашей системы. Тогда M=m .
Неравенство M m очевидно: ясно, что если в системе есть m попарно
непересекающихся отрезков, то не может существовать меньше чем m точек,
одну из которых содержал бы каждый из отрезков системы (даже на m
выбранных отрезков нужно поместить по крайней мере m точек). Осталось
доказать неравенство M
m .
Для этого достаточно доказать, что из системы всегда можно выбрать
некоторое количество k непересекающихся отрезков α1, α2,
... , αk и в каждом из них выбрать по точке A1, A2, ..., Ak
так, чтобы каждый из отрезков системы содержал одну из этих k точек.
Если мы сумеем найти такие k отрезков, то, очевидно, M k и k
m ,
откуда M
m . (На самом деле тогда обязательно M=k=m – ведь
неравенство M<m , как мы видели, невозможно.)
Покажем, как можно выбрать такие отрезки и точки.
Представим себе, что прямая расположена перед нами горизонтально. Выберем
такой отрезок α1 , левый конец которого A1 расположен правее,
чем левые концы всех других отрезков. Выбросим из системы все отрезки,
содержащие точку A1 (в частности, α1 ) (Мы считаем, что
отрезки, о которых идет речь в задаче, "замкнутые", т.е. содержат свои
концевые точки. Впрочем, утверждения, как легко убедиться, остаются
верными и для "открытых" интервалов-отрезков, которые не содержат своих
концов.) .
Ясно, что каждый из оставшихся отрезков (если такие есть) расположен целиком
левее точки A1 и заведомо не пересекается с отрезком α1 .
К оставшимся отрезкам снова применим процедуру, описанную в предыдущем
абзаце– получим отрезок α2 и точку A2 , затем– отрезок
α3 и A3 и так далее до тех пор, пока слева от левого конца
Ak отрезка αk вообще не останется ни одного отрезка нашей
системы. Отрезки α1, α2, ..., αk и точки A1, A2,
..., Ak удовлетворяют всем нашим требованиям. Теорема доказана.
Решим теперь задачу M154. Докажем, что из (pq+1) отрезков на
прямой всегда можно выбрать либо (p+1) отрезков, имеющих общую точку,
либо (q+1) попарно не пересекающихся отрезков. (При p=q=7 это и есть
утверждение задачи M154.)
Действительно, если для заданной системы из (pq+1) отрезков величина
M=m , о которой идет речь в теореме, больше q , то можно выбрать m q+1
непересекающихся отрезков, а если эта величина не больше q , то можно
выбрать множество из M
q точек, имеющее общую точку с каждым из
(pq+1) отрезков. Тогда, безусловно, какую-то одну из этих M точек
должны содержать по крайней мере (p+1) отрезков: если бы каждую точку
содержало бы не больше p отрезков, то всего отрезков было бы не больше
Mp
pq .
