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

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

Условие

Автор: Карасев Р.

На плоскости нарисовано несколько прямоугольников со сторонами, параллельными осям координат. Известно, что каждые два прямоугольника можно пересечь вертикальной или горизонтальной прямой. Докажите, что можно провести одну горизонтальную и одну вертикальную прямую так, чтобы любой прямоугольник пересекался хотя бы с одной из этих двух прямых.

Решение

Лемма. Пусть в семействе прямоугольников любые два можно пересечь вертикальной прямой. Тогда их все можно пересечь вертикальной прямой.

Доказательство. Рассмотрим прямоугольник с самой левой правой границей и прямоугольник с самой правой левой границей. По условию их можно пересечь прямой. Тогда у любого из оставшихся прямоугольников левая граница будет левее этой прямой, а правая – правее, то есть прямая пересечет все прямоугольники. Лемма доказана.

Перейдем к решению задачи. Предположим противное. Назовем два прямоугольника разделенными, если их нельзя пересечь вертикальной прямой. Рассмотрим все пары разделенных прямоугольников. В каждой паре рассмотрим прямую, на которой лежит самая нижняя из их горизонтальных сторон; пусть h – самая высокая из этих прямых. Возможны два случая.
1. Пусть не существует пары разделенных прямоугольников, лежащих ниже h . Проведем прямую h и рассмотрим все прямоугольники, не пересеченные ею. Если среди них нет пары разделенных, то по лемме их можно пересечь вертикальной прямой, и утверждение задачи доказано. Пусть такая пара прямоугольников (A,B) нашлась (см. рис.) . Тогда по предположению один из них (скажем, A ) лежит выше h . Из выбора h теперь следует, что нижняя сторона прямоугольника B лежит ниже h , а значит, и весь он лежит ниже h . Значит, эти прямоугольники нельзя пересечь ни вертикальной, ни горизонтальной прямой – противоречие.





2. Пусть существует пара (C,D) разделенных прямоугольников, лежащих ниже h . По выбору h , существуют также два разделенных прямоугольника A и B , лежащие не ниже h . Будем считать, что прямоугольник A лежит левее, чем B , а прямоугольник C – левее, чем D . Пусть для определенности правая сторона A находится не правее, чем правая сторона C (см. рис.) . Тогда прямоугольники A и D также разделены, при этом один из них лежит не ниже h , а другой – ниже h . Значит, эти два прямоугольника нельзя пересечь ни вертикальной, ни горизонтальной прямой. Противоречие.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2008
Этап
Вариант 5
Класс
Класс 10
задача
Номер 08.5.10.8

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

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