Тема . Комбинаторная геометрия

Пересечение отрезков и прямых

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела комбинаторная геометрия
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#77011

На прямой дано 2n− 1  черных и 2n− 1  белых отрезков. Каждый пересекает хотя бы n  отрезков другого цвета. Докажите, что найдется отрезок одного из двух цветов, пересекающий все отрезки другого цвета.

Подсказки к задаче

Подсказка 1

Давайте для каждого чёрного отрезка рассмотрим какой-то белый отрезок, с которым он не пересекается. Что можно про них сказать?

Подсказка 2

Проверьте для каждого из этих белых отрезков, пересекают ли они хотя бы n чëрных отрезков, или нет.

Показать доказательство

Достаточно доказать следующее утверждение: если любой белый отрезок пересекается хотя бы с n  чёрными, то найдётся чёрный, пересекающийся со всеми белыми.

Предположим противное. Выберем для каждого чёрного отрезка белый, не пересекающийся с ним. Такой белый отрезок лежит либо левее соответствующего чёрного, либо правее. Следовательно, есть хотя бы n  чёрных отрезков, для каждого из которых его белый отрезок лежит по одну и ту же сторону от него (пусть, для определённости, левее). Для каждого из этих чёрных отрезков его левый конец лежит правее правого конца соответствующего ему белого отрезка.

Тогда, если мы выберем из правых концов белых отрезков самый левый, то он будет левее хотя бы n  левых концов чёрных отрезков, то есть этот белый отрезок не будет пересекаться ни с одним из этих n  отрезков. Противоречие.

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!