Раскраски

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

Закрасим клетки во втором, четвертом, шестом и так далее горизонтальном ряду, например, снизу вверх, причем закрашиваем в каждом ряду вторую, четвертую, шестую и так далее клеточки, например, слева направо (см. рис.). Закрашенных клеточек получится

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

Пример. Укладываем у стороны длиной вплотную друг к другу слева направо ряд из квадратов; следующий ряд из квадратов выкладываем со сдвигом на клетку вверх и вправо, следующий ряд — со сдвигом вверх и влево, и так далее (см. рис.).