Назад
Задача

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

Решение

Будем последовательно выбрасывать отрезки, покрытые одним или несколькими оставшимися отрезками, до тех пор, пока это возможно. Направим ось координат по данному отрезку и обозначим координаты концов оставшихся отрезков черезakиbk(ak<bk). Один из двух отрезков с общим левым концом всегда будет выброшен, поэтому можно считать, чтоa1<a2<a3< ... <an. Докажем, что тогдаbk<ak + 2, т. е. четные отрезки не пересекаются и нечетные тоже. Предположим, чтоbk$\ge$ak + 2. Возможны два случая. 1.bk + 1$\le$bk + 2, тогда отрезок с номеромk+ 1 покрыт отрезками с номерамиkиk+ 2. Получено противоречие. 2.bk + 1$\ge$bk + 2, тогда отрезок с номеромk+ 2 покрыт отрезком с номеромk+ 1. Получено противоречие. Остается заметить, что сумма длин либо четных, либо нечетных отрезков не меньше 0,5.

Ответ

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

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

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