ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 66567
Темы:    [ Примеры и контрпримеры. Конструкции ]
[ Раскраски ]
[ Комбинаторная геометрия (прочее) ]
Сложность: 5
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Для каких $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$.

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Номер 83
Год 2020
класс
Класс 10
задача
Номер 6

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .