Задача 35444

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

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

Условие

Коридор покрыт несколькими ковровыми дорожками (возможно, с наложениями). Докажите, что можно убрать несколько дорожек таким образом, чтобы оставшиеся дорожки покрывали коридор и сумма их длин не превышала удвоенной длины коридора.

Подсказка

Рассмотрите минимальную систему дорожек, покрывающих весь коридор. Покажите, что в каждом наложении участвуют не более двух дорожек.

Решение

Переформулируем задачу следующим образом. Пусть отрезок длины 1 покрыт отрезками. Требуется доказать, что можно исключить из покрытия некоторые отрезки так, чтобы оставшиеся отрезки по-прежнему покрывали отрезок и их суммарная длина не превышала 2. Рассмотрим минимальное подмножество M отрезков, покрывающее данный отрезок. Требование минимальности означает, что если из подмножества M удалить любой отрезок, то полученная система отрезков уже не будет покрывать исходный отрезок длины 1. Докажем, что каждая точка отрезка длины 1 покрывается не более, чем двумя отрезками множества М - этого будет достаточно для решения задачи. Предположим противное - некоторая точка X покрыта тремя отрезками [A₁, B₁], [A₂, B₂], [A₃, B₃] множества М. Пусть A_i - точка, наиболее удаленная от точки X среди трех левых концов отрезков, а B_j] - точка, наиболее удаленная от точки X среди трех правых концов отрезков. Тогда отрезок [A_i, B_j] является объединением данных трех отрезков, но он является и объединением не более чем двух из данных трех отрезков (а именно, отрезков [A_i, B_i], [A_j, B_j]). Таким образом, один из трех отрезков [A₁, B₁], [A₂, B₂], [A₃, B₃] множества М лежит в объединении двух других, что противоречит определению множества M.

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

web-сайт

задача