Задание по олимпиадной математике: черные клетки на плоскости

Решение 1:   Закрасим чёрным сначала $k$ клеток, стоящих подряд вдоль одной из диагоналей, идущей вправо-вниз. Затем сдвинем эту картинку по диагонали вправо-вверх на  $k, 2k, 3k, ..., (k - 1)k$  клеток. Получится множество $A$ из $k^2$ чёрных клеток, которое каждая горизонталь и вертикаль пересекает не более чем по одной клетке, а каждая диагональ имеет с $A$ либо 0, либо $k$ общих клеток (рисунок слева для  $k$ = 3).   При этом всё множество $A$ лежит в квадрате $k^2\times k^2$.

              Заметим, что если квадрат $n\times n$ сдвинуть на 2$n$ клеток по вертикали, то не существует диагонали, пересекающей оба эти квадрата (рисунок справа для  $n$ = 3).

  Поэтому, сдвинув множество $A$ на  $2k^2, 4k^2, ..., 2(k-1)k^2$  вверх, мы получим множество $B$ из $k^3$ чёрных клеток, которое каждая горизонталь пересекает не более чем по одной клетке, а каждая вертикаль и диагональ имеет с $B$ либо 0, либо $k$ общих клеток. При этом все множество $B$ лежит в квадрате $2k^3\times 2k^3$.

  Теперь, сдвинув множество $B$ на  $4k^3, 8k^3, ..., 4(k-1)k^3$  вправо, мы получим искомое множество из $k^4$ чёрных клеток.

 (Другими словами, построенное множество состоит из клеток с "координатами"  $(- i+kj+4mk^3, i+kj+2nk^2), 0\leqslant i, j, m, n < k$.)

Решение 2:   Есть 4 вида линий. Линии, на которых есть чёрные клетки, назовём покрываемыми. Требуется, чтобы на каждой покрываемой линии было ровно по $k$ чёрных клеток.

  Набор чёрных клеток, для которого на каждой покрываемой линии содержится ровно $k$ клеток, назовём k-набором. Из $k$-набора можно получить 2$k$-набор. Для этого вырежем квадрат, содержащий

$k$-набор, и разместим его копии в квадратах, отмеченных буквами на рисунке.

  Назовём $k$-набор супернабором, если его можно разбить на 1-наборы с тем же множеством покрываемых линий у каждого. Указанный выше метод из $k$-супернабора строит 2$k$-супернабор. Действительно, разобьём $k$-супернабор на 1-наборы. Возьмём один из них. Его копии на однобуквенных местах образуют 1-набор, который покрывает то же множество линий, что и 2$k$-набор. Весь

2$k$-набор разобьётся на такие 1-наборы, значит, это 2$k$-супернабор.

  В $k$-супернаборе легко выделить $l$-набор для любого  $l\leqslant k$:  взять в нём $l$ разных 1-наборов с тем же множеством покрывающих линий у каждого. Осталось заметить, что 1-супернабор существует: он состоит, например, из одной клетки.