Задача 109789
|
|
 |
Условие
На прямой расположены 2k-1 белый и 2k-1 черный отрезок. Известно, что любой белый отрезок пересекается хотя бы с k черными, а любой черный – хотя бы с k белыми. Докажите, что найдутся черный отрезок, пересекающийся со всеми белыми, и белый отрезок, пересекающийся со всеми черными.Решение
Достаточно доказать следующее утверждение: если любой белый отрезок пересекается хотя бы с k черными, то найдется черный, пересекающийся со всеми белыми.Предположим противное. Выберем для каждого черного отрезка белый, не пересекающийся с ним. Такой белый отрезок лежит либо левее соответствующего черного, либо правее его. Следовательно, есть хотя бы k черных отрезков, для каждого из которых его белый отрезок лежит по одну и ту же сторону от него (пусть, для определенности, левее). Для каждого из этих черных отрезков его левый конец лежит правее правого конца соответствующего ему белого отрезка. Тогда, если мы выберем из правых концов белых отрезков самый левый, то он будет лежать левее хотя бы k левых концов черных отрезков, т.е. этот белый отрезок не будет пересекаться ни с одним из этих k отрезков. Противоречие.
