Назад
Задача

Несколько отрезков покрывают отрезок  [0, 1].

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

Решение

  Используем индукцию по числу отрезков, покрывающих отрезок  [0, 1].

  База. Для покрытия одним отрезком утверждение очевидно.

  Шаг индукции. Пусть отрезок  [0, 1]  покрыт  n + 1  отрезком. Если среди них имеется отрезок, который покрыт остальными, то выкинем его из покрытия и воспользуемся предположением индукции.

  Пусть таких отрезков нет. Обозначим отрезки  Ii = [ai, bi]  так, что  a1 < a2 < ... < an.  Тогда  bi < bi+1  для каждого i. С другой стороны,  bi < ai+2,  иначе отрезки Ii и Ii+2 покрывали бы отрезок Ii+1.  Значит, отрезки с нечётными номерами попарно не пересекаются, как и отрезки с чётными номерами. Поскольку все отрезки образуют покрытие отрезка  [0, 1],  либо сумма длин отрезков с чётными номерами, либо сумма длин отрезков с нечётными номерами не меньше ½. Тем самым найдена искомая система непересекающихся отрезков.

Ответ

Ответ задачи отсутствует

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Комментариев нет