ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 35444
Темы:    [ Покрытия ]
[ Системы отрезков, прямых и окружностей ]
[ Принцип крайнего (прочее) ]
Сложность: 4-
Классы: 9,10
В корзину
Прислать комментарий

Условие

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

Подсказка

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

Решение

Переформулируем задачу следующим образом. Пусть отрезок длины 1 покрыт отрезками. Требуется доказать, что можно исключить из покрытия некоторые отрезки так, чтобы оставшиеся отрезки по-прежнему покрывали отрезок и их суммарная длина не превышала 2. Рассмотрим минимальное подмножество M отрезков, покрывающее данный отрезок. Требование минимальности означает, что если из подмножества M удалить любой отрезок, то полученная система отрезков уже не будет покрывать исходный отрезок длины 1. Докажем, что каждая точка отрезка длины 1 покрывается не более, чем двумя отрезками множества М - этого будет достаточно для решения задачи. Предположим противное - некоторая точка X покрыта тремя отрезками [A1, B1], [A2, B2], [A3, B3] множества М. Пусть Ai - точка, наиболее удаленная от точки X среди трех левых концов отрезков, а Bj] - точка, наиболее удаленная от точки X среди трех правых концов отрезков. Тогда отрезок [Ai, Bj] является объединением данных трех отрезков, но он является и объединением не более чем двух из данных трех отрезков (а именно, отрезков [Ai, Bi], [Aj, Bj]). Таким образом, один из трех отрезков [A1, B1], [A2, B2], [A3, B3] множества М лежит в объединении двух других, что противоречит определению множества M.

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

web-сайт
задача

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .