Задача 58268

Темы:    [ Покрытия ] [ Системы отрезков, прямых и окружностей ] [ Упорядочивание по возрастанию (убыванию) ] [ Принцип Дирихле (углы и длины) ]

Сложность: 5- Классы: 8,9

Условие

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

Решение

Будем последовательно выбрасывать отрезки, покрытые одним или несколькими оставшимися отрезками, до тех пор, пока это возможно. Направим ось координат по данному отрезку и обозначим координаты концов оставшихся отрезков через a_k и b_k (a_k < b_k). Один из двух отрезков с общим левым концом всегда будет выброшен, поэтому можно считать, что a₁ < a₂ < a₃ < ... < a_n. Докажем, что тогда b_k < a_{k + 2}, т. е. четные отрезки не пересекаются и нечетные тоже. Предположим, что b_ka_{k + 2}. Возможны два случая.
1. b_{k + 1}b_{k + 2}, тогда отрезок с номером k + 1 покрыт отрезками с номерами k и k + 2. Получено противоречие.
2. b_{k + 1}b_{k + 2}, тогда отрезок с номером k + 2 покрыт отрезком с номером k + 1. Получено противоречие.
Остается заметить, что сумма длин либо четных, либо нечетных отрезков не меньше 0,5.

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

книга
Автор	Прасолов В.В.
Год издания	2001
Название	Задачи по планиметрии
Издательство	МЦНМО
Издание	4*
глава
Номер	25
Название	Разрезания, разбиения, покрытия
Тема	Разрезания, разбиения, покрытия и замощения
параграф
Номер	8
Название	Покрытия
Тема	Покрытия
задача
Номер	25.046