При каких натуральных $m$ и $n$ ($m\lt n$) можно закрасить некоторые клетки бесконечного листа клетчатой бумаги в чёрный цвет так, чтобы любой прямоугольник размера $m\times n$ содержал ровно одну чёрную клетку? Начните с более простой задачи: рассмотрите случаи $m=2$ и $n=3$, 4, 5.
Докажем, что требуемая раскраска клетчатой плоскости для пары $(m,n)$, $m\lt n$ существует в том и только в том случае, когда $n$ делится на $m$.
Если раскраска плоскости такова, что в любом ряде (вертикальном и горизонтальном) закрашена чёрным каждая $k$-я по счёту клетка (как на рисунке 1, где $k=3$), то в любом прямоугольнике $1\times k$ будет ровно одна чёрная клетка. Из такой периодической раскраски для пары $(1,k)$ нетрудно получить периодическую раскраску для пары $(m,km)$: нужно измельчить в $m$ раз сетку и в каждой чёрной клетке старой (крупной) решётки оставить чёрной только одну, — скажем, левую нижнюю клетку (рисунок 2 получен из рисунка 1 именно таким приёмом; здесь $k=3$, $m=2$). Итак, мы показали, как построить нужную раскраску для пары $(m,n)$, если $n$ делится на $m$.
Рис. 1Рис. 2
Предположим теперь, что для пары $(m,n)$, где $n$ не делится на $m$ ($n\gt m\gt1$), построена нужная раскраска, и придём к противоречию.
Рассмотрим два случая.
1) Пусть $n\le2m-1$. Если два вертикально расположенных прямоугольника $m\times n$ имеют общую угловую чёрную клетку, как показано на рисунке 3, то в их объединении больше не может быть чёрных клеток. Но в нём можно разместить горизонтальный (красный) прямоугольник $n\times m$, не содержащий чёрной клетки. Противоречие.
2) Пусть $n\gt2m-1$. Докажем сначала, что если $K$ — чёрная клетка, то $n\cdot n$ клетка в том же ряду (считая от $K$) — тоже чёрная. Рассмотрим два вертикально расположенных прямоугольника $m\times n$ с общей нижней угловой клеткой $K$ и ещё два прямоугольника, полученные из них сдвигом на одну клетку вверх (голубой и жёлтый на рисунке 4). Поскольку в них должно быть по одной чёрной клетке, то чёрным цветом должны быть закрашены либо одна из жёлтых клеток и одна из голубых, либо одна зелёная клетка. Но первая возможность исключена, так как в горизонтальном красном прямоугольнике не может быть двух чёрных клеток; значит, зелёную клетку нужно закрасить в чёрный цвет.
Рис. 3Рис. 4Рис. 5
Рассмотрим теперь квадрат $n\times n$ с чёрной клеткой в нижнем левом углу. Если $n=mk+r$, где $0\lt r\lt m$, то квадрат можно разрезать на $k$ горизонтальных прямоугольников $n\times m$ и «остаток» — прямоугольник $r\times n$ (рис. 5). Рассматривая эти $k$ прямоугольники, а также прямоугольники, полученные из них сдвигом на одну клетку вверх, мы последовательно убедимся, что в нижней (жёлтой) полоске каждого прямоугольника должна быть чёрная клетка. Но тогда в красном прямоугольнике будет две чёрные клетки. Противоречие.
