ВсОШ 2024, 10 класс, задача 7
Пусть даны натуральные числа и . На прямой даны белых отрезков и чёрных отрезков, при этом и . Известно, что никакие два отрезка одного цвета не пересекаются (даже не имеют общих концов). Также известно, что при любом выборе белых отрезков и чёрных отрезков обязательно какая-то пара выбранных отрезков будет пересекаться. Докажите, что . (Г. Челноков)
Ответ
Первое решение. Пронумеруем белые отрезки слева направо как , а чёрные - как . Для каждого чёрного отрезка назовём его силой количество индексов таких, что пересекается как с , так и с . Если с какой-то парой пересекаются два чёрных отрезка, то они имеют общую точку, что невозможно по условию. Поэтому каждая такая пара учтена в силе не более, чем одного чёрного отрезка, а значит,
.
Рассмотрим следующие групп, состоящих из белых отрезков каждая: при группа состоит из отрезков , а при группа состоит из отрезков , а также из (иначе говоря, каждая группа состоит из последовательных отрезков в циклическом порядке). Для группы обозначим через количество чёрных отрезков, не пересекающихся ни с одним из отрезков в . По условию, ; поэтому
.
С другой стороны, каждый чёрный отрезок пересекается максимум с белыми отрезками, и все эти белые отрезки расположены подряд. Тогда количество групп, содержащих хотя бы один из этих белых отрезков, не превосходит . Поэтому отрезок учтён хотя бы в числах вида . Поэтому
.
Из полученных двух оценок на вытекает, что
,
что и требовалось доказать.
Второе решение. Предположим, что утверждение задачи для некоторых неверно: , и при этом условии сумма - минимальная возможная. Без ограничения общности тогда . Возьмём -й слева белый отрезок и -й слева чёрный отрезок . У какого-то из них правый конец левее.
-
Пусть правый конец левее (или концы совпадают). Тогда правые чёрных отрезков не пересекаются с левыми белыми. Противоречие.
-
Пусть правый конец левее. Выкинем все белые отрезки слева от (включая его) и все чёрные отрезки слева от (включая его). Оставшиеся белые отрезки (их хотя бы ) не пересекаются с выкинутыми чёрными; отсюда уже следует, что .
Положим , , и ; тогда осталось белых и чёрных отрезков. Рассмотрим любые оставшихся белых и оставшихся чёрных отрезков. Если среди них нет пересекающихся, то, добавив к ним все выкинутые чёрные отрезки, получим набор из белых и чёрных отрезков исходного набора, среди которых нет пересекающихся; это невозможно. Значит, оставшийся набор удовлетворяет условию (для новых чисел и ), при этом в нём меньше отрезков, чем в исходном, поэтому
.
Противоречие.
Замечание. Отметим, что при утверждение задачи превращается в двухцветную (одномерную) теорему Хелли.