Олимпиадная задача по комбинаторной геометрии: Найдите отрезок, пересекающий все остальные
Задача
На прямой имеется2n+1отрезок. Любой отрезок пересекается по крайней мере с n другими. Докажите, что существует отрезок, пересекающийся со всеми остальными.
Решение
Пронумеруем все правые концы отрезков слева направо, а затем также слева направо – все левые концы. Рассмотрим все отрезки, у которых правый конец имеет номер больше n . Из всех таких отрезков выберем тот, у которого левый конец имеет наименьший номер. Полученный отрезок и будет искомым. Действительно, если есть отрезок правее его, то он не пересекается с отрезками, имеющими правые концы с номерами1,2,..,n+1, а если есть левее – то с отрезками, имеющими правые концы с номерами n+1,n+2,..,2n+1.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет