Назад
Задача

Для каких $k$ можно закрасить на белой клетчатой плоскости несколько клеток (конечное число, большее нуля) в черный цвет так, чтобы на любой клетчатой вертикали, горизонтали и диагонали либо было ровно $k$ черных клеток, либо вовсе не было черных клеток?

Решение

Рассмотрим множество клеток $A_1$, которое является вертикальным отрезком длины $k$. Заметим, что каждый столбец пересекает $A_1$ по 0 или $k$ клеткам, а каждая строка или диагональ — по 0 или 1 клетке.

Рассмотрим множество $A_2$, которое состоит из $k$ копий отрезка $A_1$, каждая из которых получается из предыдущей переносом на вектор $(k ,0)$. Таким образом, $A_2$ состоит из $k$ отрезков длины $k$, разделённых $k-1$ пустыми столбцами. Заметим, что любая строка или столбец пересекают $A_2$ по 0 или $k$ клеткам, а каждая диагональ — по 0 или 1 клетке (так как никакая диагональ не пересекает две копии $A_1$ в $A_2$).

Множество $A_3$ состоит из $k$ копий $A_2$, каждая из которых получается переносом предыдущей на вектор $(k^2,k^2)$. Любая строка, столбец или диагональ, параллельная вектору $(1,-1)$, пересекает не более одной копии $A_2$ в $A_3$, а любая диагональ, параллельная вектору $(1,1)$, либо не пересекает ни одной, либо пересекает все копии $A_2$ в $A_3$. Следовательно, строки, столбцы и диагонали, параллельные вектору $(1,1)$, пересекают 0 или $k$ клеток из $A_3$, а диагонали, параллельные вектору $(1,-1)$ пересекают 0 или 1 клетку.

Аналогично построим множество $A_4$: оно состоит из $k$ копий $A_3$, каждая из которых получается переносом на вектор $(k^3,-k^3)$ из предыдущей. Любая строка, столбец или диагональ, параллельная вектору $(1,1)$, пересекает не более одной копии $A_3$ в $A_4$, а любая диагональ, параллельная вектору $(1,-1)$, либо не пересекает ни одной, либо пересекает все копии. Следовательно, любая строка, столбец или диагональ пересекает $A_4$ по 0 или $k$ клеткам.

Замечание. Получившийся пример можно рассматривать как проекцию узлов $4$-мерного куба $k\times k\times k\times k$ на плоскость.

Ответ

При любых $k$.

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Комментариев нет