Принцип крайнего, индукция и другие методы в комбигео
Ошибка.
Попробуйте повторить позже
Коридор длины 
произвольным образом покрыли дорожками (конечным числом). Докажите, что можно убрать некоторые дорожки так,
чтобы оставшиеся дорожки покрывали весь коридор, и их суммарная длина не превышала 
Подсказка 1
Попробуем рассмотреть минимальное множество дорожек, покрывающее коридор. Можно ли понять, сколькими дорожками может покрываться одна точка коридора?
Подсказка 2
Предположим, что некоторая точка Y накрыта тремя дорожками. Как доказать, что один из отрезков можно убрать?
Подсказка 3
Верно! Посмотрим на самую удаленную от Y правую границу всех дорожек и самую удаленную от нее левую границу. Тогда легко понять, что все множество, покрывающее Y, может быть покрыто всего двумя отрезками! Какой вывод можно сделать?
Рассмотрим минимальное множество дорожек 
покрывающее весь коридор. Требование минимальности означает, что при удалении
любой дорожки из 
оно перестаёт покрывать коридор.
Покажем, что каждая точка коридора покрывается не более, чем двумя отрезками из 
(нетрудно понять, что этого достаточно для
решения задачи). Предположим противное, пусть некоторая точка 
покрыта тремя отрезками 
множества 
Пусть
— точка, наиболее удалённая от 
среди трёх правых концов отрезков, а 
— среди трёх левых. Тогда отрезок 
является
объединением данных трёх отрезков, но он является объединением не более чем двух из данных трёх отрезков (а именно, отрезков 
и
). Таким образом, один из трёх отрезков 
множества 
лежит в объединении двух других, что противоречит
выбору множества 
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
