Задача 35538

Темы:    [ Покрытия ] [ Индукция (прочее) ] [ Системы отрезков, прямых и окружностей ]

Сложность: 4- Классы: 9,10,11

Условие

Несколько отрезков покрывают отрезок  [0, 1].
Докажите, что среди них можно выбрать несколько непересекающихся отрезков, сумма длин которых не меньше ½.

Подсказка

Начните выбрасывать отрезки, которые покрываются другими отрезками.

Решение

  Используем индукцию по числу отрезков, покрывающих отрезок  [0, 1].
  База. Для покрытия одним отрезком утверждение очевидно.
  Шаг индукции. Пусть отрезок  [0, 1]  покрыт  n + 1  отрезком. Если среди них имеется отрезок, который покрыт остальными, то выкинем его из покрытия и воспользуемся предположением индукции.
  Пусть таких отрезков нет. Обозначим отрезки  I_i = [a_i, b_i]  так, что  a₁ < a₂ < ... < a_n.  Тогда  b_i < b_i+1  для каждого i. С другой стороны,  b_i < a_i+2,  иначе отрезки I_i и I_i+2 покрывали бы отрезок I_i+1.  Значит, отрезки с нечётными номерами попарно не пересекаются, как и отрезки с чётными номерами. Поскольку все отрезки образуют покрытие отрезка  [0, 1],  либо сумма длин отрезков с чётными номерами, либо сумма длин отрезков с нечётными номерами не меньше ½. Тем самым найдена искомая система непересекающихся отрезков.

Источники и прецеденты использования

web-сайт

задача