Принцип крайнего, индукция и другие методы в комбигео

Обозначим число прямоугольников через Рассмотрим самую нижнюю из верхних границ прямоугольников (назовём прямую, на которой она лежит — а прямоугольник — ). Есть не более чем прямоугольников таких, что их нижняя граница лежит выше так как все такие прямоугольники не пересекаются с Назовём такие прямоугольники нижнеплохими. Аналогично определим верхнеплохие, левоплохие и правоплохие прямоугольники.

Заметим, что поскольку то существует прямоугольник не являющийся нижне-, верхне-, лево- или правоплохим. Но тогда он пересекается со всеми прямоугольниками.

В самом деле: пусть с ним не пересекается какой-то прямоугольник тогда либо какая-то горизонтальная, либо какая-то вертикальная прямая разделяет и Если, например, она горизонтальна и прямоугольник лежит выше неё, то верхняя граница лежит ниже нижней границы что невозможно по построению. Остальные три случая аналогичны.