Раскраски

Если делится нацело то можно разделить всё только на прямоугольники Их будет штук, если обозначить

Если даёт остаток при делении на то обозначим так же и покажем, что делится нацело на

Пронумеруем строки сверху вниз и покрасим строку в цвет остатка её номера по модулю Тогда на доске клеток каждого цвета и клеток каждого цвета

Рассмотрим произвольное разрезание на прямоугольники. Пусть в разрезании участвуют прямоугольников Перекрасим все клетки, покрытые этими прямоугольниками в -ый цвет. Каждый из прямоугольников содержит по одной клетке каждого из цветов. Тогда на доске клеток каждого цвета и клеток каждого цвета которые покрыты фигурами

Заметим, что каждая из фигур покрывает клетки фиксированного цвета. Тогда кратно и кратно Наконец, кратно Значит, в этом случае можно разделить всё на прямоугольники