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

Спроецируем все прямоугольники на оси координат. Рассмотрим сначала проекции на ось для каждого прямоугольника получим отрезок Выберем:

• Самый левый из всех правых концов проекций:
• Самый правый из всех левых концов проекций:

Заметим, что точка принадлежит как минимум отрезку. Аналогично, точка принадлежит как минимум отрезку. Тогда общее количество отрезков, содержащих хотя бы одну из этих точек, не менее

Поскольку всего отрезков то количество отрезков, содержащих обе точки и будет:

Заметим, что такие отрезки пересекают все остальные, так как в них полностью лежит отрезок а его все пересекают по выбору Аналогичные рассуждения проводим для проекций на ось

Суммарное количество “хороших” проекций на обеих осях:

Покажем, что это число превышает общее количество прямоугольников:

Это неравенство выполняется, так как для целой части справедливо:

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