Принцип крайнего, индукция и другие методы в комбигео
Ошибка.
Попробуйте повторить позже
Дано прямоугольников с параллельными сторонами. Каждый пересекает хотя бы
других. Докажите, что существует
прямоугольник, пересекающий все остальные.
Подсказка
Давайте рассмотрим некоторый прямоугольник A и подумаем, сколько может быть прямоугольников, у которых нижняя сторона выше верхней стороны A. Такие прямоугольники точно не пересекаются с A. А какие ещё прямоугольник не пересекаются с А?
Обозначим число прямоугольников через Рассмотрим самую нижнюю из верхних границ прямоугольников (назовём прямую, на которой
она лежит —
а прямоугольник —
). Есть не более чем
прямоугольников таких, что их нижняя граница лежит выше
так
как все такие прямоугольники не пересекаются с
Назовём такие прямоугольники нижнеплохими. Аналогично определим верхнеплохие,
левоплохие и правоплохие прямоугольники.
Заметим, что поскольку то существует прямоугольник
не являющийся нижне-, верхне-, лево- или правоплохим. Но
тогда он пересекается со всеми прямоугольниками.
В самом деле: пусть с ним не пересекается какой-то прямоугольник тогда либо какая-то горизонтальная, либо
какая-то вертикальная прямая разделяет
и
Если, например, она горизонтальна и прямоугольник
лежит выше
неё, то верхняя граница
лежит ниже нижней границы
что невозможно по построению. Остальные три случая
аналогичны.
Специальные программы

Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!

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

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

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

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

Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!