Принцип крайнего, индукция и другие методы в комбигео

Первое решение. Пронумеруем белые отрезки слева направо как …, а чёрные — как …, Для каждого чёрного отрезка назовём его силой количество индексов таких, что пересекается как с так и с Если с какой-то парой пересекаются два чёрных отрезка, то они имеют общую точку, что невозможно по условию. Поэтому каждая такая пара учтена в силе не более, чем одного чёрного отрезка, а значит,

Рассмотрим следующие групп, состоящих из белых отрезков каждая: при группа состоит из отрезков …, а при группа состоит из отрезков …, а также из …, (иначе говоря, каждая группа состоит из последовательных отрезков в циклическом порядке). Для группы обозначим через количество чёрных отрезков, не пересекающихся ни с одним из отрезков в По условию, поэтому

С другой стороны, каждый чёрный отрезок пересекается максимум белыми отрезками, и все эти белые отрезки расположены подряд. Тогда количество групп, содержащих хотя бы один из этих белых отрезков, не превосходит

Поэтому отрезок учтён хотя бы в числах вида Поэтому

Из полученных двух оценок на сумму вытекает, что

что и требовалось доказать.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Предположим, что утверждение задачи для некоторых неверно:

и при этом условии сумма — минимальная возможная.

Без ограничения общности тогда Возьмём -й слева белый отрезок и -й слева чёрный отрезок У какого-то из них правый конец левее.

1) Пусть правый конец левее (или концы совпадают). Тогда правые чёрных отрезков не пересекаются с левыми белыми. Противоречие.

2) Пусть правый конец левее. Выкинем все белые отрезки слева от (включая его) и все чёрные отрезки слева от (включая его). Оставшиеся белые отрезки (их хотя бы ) не пересекаются с выкинутыми чёрными; отсюда уже следует, что

Положим

и

тогда осталось белых и чёрных отрезков. Рассмотрим любые оставшихся белых и оставшихся чёрных отрезков. Если среди них нет пересекающихся, то, добавив к ним все выкинутые чёрные отрезки, получим набор из белых и

чёрных отрезков исходного набора, среди которых нет пересекающихся; это невозможно. Значит, оставшийся набор удовлетворяет условию для новых чисел и при этом в нём меньше отрезков, чем в исходном, поэтому

Противоречие.