Выбрана 1 задача 
Версия для печати
Убрать все задачи
Решение
Убрать все задачи
В некотором государстве было 2002 города, соединённых дорогами так, что если запретить проезд через любой из городов, то из каждого из оставшихся городов можно добраться до любого другого. Каждый год король выбирает некоторый несамопересекающийся циклический маршрут и приказывает построить новый город, соединить его дорогами со всеми городами выбранного маршрута, а все дороги этого маршрута закрыть за ненадобностью. Через несколько лет в стране не осталось ни одного несамопересекающегося циклического маршрута, проходящего по ее городам. Докажите, что в этот момент количество городов, из которых выходит ровно одна дорога, не меньше 2002.
Решение
Задача 111876
|
|
 |
Условие
На плоскости нарисовано несколько прямоугольников со сторонами, параллельными осям координат. Известно, что каждые два прямоугольника можно пересечь вертикальной или горизонтальной прямой. Докажите, что можно провести одну горизонтальную и одну вертикальную прямую так, чтобы любой прямоугольник пересекался хотя бы с одной из этих двух прямых.Решение
Лемма. Пусть в семействе прямоугольников любые два можно пересечь вертикальной прямой. Тогда их все можно пересечь вертикальной прямой.Доказательство. Рассмотрим прямоугольник с самой левой правой границей и прямоугольник с самой правой левой границей. По условию их можно пересечь прямой. Тогда у любого из оставшихся прямоугольников левая граница будет левее этой прямой, а правая – правее, то есть прямая пересечет все прямоугольники. Лемма доказана.
Перейдем к решению задачи. Предположим противное. Назовем два прямоугольника разделенными, если их нельзя пересечь вертикальной прямой. Рассмотрим все пары разделенных прямоугольников. В каждой паре рассмотрим прямую, на которой лежит самая нижняя из их горизонтальных сторон; пусть 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 . Значит, эти два прямоугольника нельзя пересечь ни вертикальной, ни горизонтальной прямой. Противоречие.
