Условие
Коридор покрыт несколькими ковровыми дорожками
(возможно, с наложениями).
Докажите, что можно убрать несколько дорожек таким образом, чтобы
оставшиеся дорожки покрывали коридор и сумма их длин не превышала
удвоенной длины коридора.
Подсказка
Рассмотрите минимальную систему дорожек, покрывающих весь коридор.
Покажите, что в каждом наложении участвуют не более двух дорожек.
Решение
Переформулируем задачу следующим образом.
Пусть отрезок длины 1 покрыт отрезками. Требуется доказать, что можно
исключить из покрытия некоторые отрезки так, чтобы оставшиеся
отрезки по-прежнему покрывали отрезок и их суммарная длина не
превышала 2.
Рассмотрим минимальное подмножество M отрезков, покрывающее данный
отрезок. Требование минимальности означает, что если из
подмножества M удалить любой отрезок, то полученная система отрезков уже
не будет покрывать исходный отрезок длины 1.
Докажем, что каждая точка отрезка длины 1 покрывается не более,
чем двумя отрезками множества М - этого будет достаточно для
решения задачи.
Предположим противное - некоторая точка X покрыта тремя отрезками
[A
1, B
1],
[A
2, B
2],
[A
3, B
3] множества М.
Пусть A
i - точка, наиболее удаленная от точки X среди трех
левых концов отрезков, а B
j]
- точка, наиболее удаленная от точки X среди трех
правых концов отрезков.
Тогда отрезок [A
i, B
j]
является объединением данных трех отрезков,
но он является и объединением не более чем двух из данных трех отрезков
(а именно, отрезков [A
i, B
i],
[A
j, B
j]).
Таким образом, один из трех отрезков
[A
1, B
1],
[A
2, B
2],
[A
3, B
3] множества М
лежит в объединении двух других, что противоречит
определению множества M.
Источники и прецеденты использования