Можно считать, что число квадратов $n\gt 4$, поскольку при $n \le 4$ утверждение очевидно. Рассмотрим наименьший прямоугольник $\varPi$ со сторонами, параллельными осям, содержащий все квадраты. По крайней мере одна его сторона — её можно считать горизонтальной (параллельной оси $Ox$) — больше 3. В самом деле, предположим, что вертикальная сторона не больше 3. Тогда каждый из $n$ данных квадратов можно двигать вверх или вниз не задевая остальных (поскольку либо под ним, либо над ним нет квадрата). Передвинув каждый квадрат вплотную к одной из горизонтальных сторон $\varPi$, мы получим, что (при $n\gt 4$) к одной из этих сторон прилегает не менее 3 квадратов, и, значит, длина горизонтальной стороны больше 3.
Пусть $M$ и $N$ — два квадрата из данных $n$. Будем говорить, что они расположены горизонтально (вертикально) и писать $M-N$ (соответственно, $M\mid N$), если их пересекает некоторая горизонтальная (вертикальная) прямая; по условию, для любой пары $M$ и $N$ квадратов всегда выполнено ровно одно из этих отношений. Пусть далее $X$ и $Y$ — самый левый и самый правый квадраты (прилежащие к сторонам $\varPi$). Разумеется, $X-Y$. Для определённости считаем, что $Y$ лежит не ниже $X$.
Существует не более одного квадрата $Z$ такого, что $Z\mid X$. (Он по горизонтали должен отстоять от $X$ не более чем на 1, поэтому $Z-Y$; так что центр $Z$ должен лежать в прямоугольнике, закрашенном на рисунке 1.)
Рисунок номер 1
Рассмотрим два случая.
1) Такого $Z$ нет, т. е. $Z-X$ для любого $Z$. Рассмотрим самый верхний квадрат $T$; пусть $t$ — прямая, идущая по его нижней стороне. Для всех квадратов $V$, лежащих ниже $t$, должны быть выполнены условия $V\mid T$ и $X-T$, поэтому их центры лежат в прямоугольнике с горизонтальной стороной 2, закрашенном на рисунке 2. Ясно, что таких квадратов не более 2 (в левой и в правой половине прямоугольника лежит центр не более чем одного квадрата). Таким образом, прямая $t$ — искомая.
Рисунок номер 2
2) Имеется такой (единственный) квадрат $Z$, что $Z\mid X$. Он лежит выше $X$ (поскольку $Z-Y$). Пусть теперь прямая $t$ проходит по верхней стороне $X$. Выше $t$ расположен только $Z$. Если некоторый квадрат $N$ расположен ниже $t$, то $Z\mid N$ (поскольку $Z-N$ неверно) и $X-N$, так что центр $N$ находится в прямоугольнике, закрашенном на рисунке З. Таких квадратов $N$ не больше чем 1, и прямая $t$ — искомая.
Рисунок номер 3
