МОШ 2020, 10 класс, задача 6
Для каких можно закрасить на белой клетчатой плоскости несколько клеток (конечное число, большее нуля) в черный цвет так, чтобы на любой клетчатой вертикали, горизонтали и диагонали либо было ровно черных клеток, либо вовсе не было черных клеток?
Ответ
Ответ. При любых .
Решение. Рассмотрим множество клеток , которое является вертикальным отрезком длины . Заметим, что каждый столбец пересекает по или клеткам, а каждая строка или диагональ — по или клетке.
Рассмотрим множество , которое состоит из копий отрезка , каждая из которых получается из предыдущей переносом на вектор . Таким образом, состоит из отрезков длины , разделённых пустыми столбцами. Заметим, что любая строка или столбец пересекают по или клеткам, а каждая диагональ — по или клетке (так как никакая диагональ не пересекает две копии в ).
Множество состоит из копий , каждая из которых получается переносом предыдущей на вектор . Любая строка, столбец или диагональ, параллельная вектору , пересекает не более одной копии в , а любая диагональ, параллельная вектору , либо не пересекает ни одной, либо пересекает все копии в . Следовательно, строки, столбцы и диагонали, параллельные вектору , пересекают или клеток из , а диагонали, параллельные вектору , пересекают или клетку.
Аналогично построим множество : оно состоит из копий , каждая из которых получается переносом на вектор из предыдущей. Любая строка, столбец или диагональ, параллельная вектору , пересекает не более одной копии в , а любая диагональ, параллельная вектору , либо не пересекает ни одной, либо пересекает все копии. Следовательно, любая строка, столбец или диагональ пересекает по или клеткам.
Замечание. Получившийся пример можно рассматривать как проекцию узлов -мерного куба на плоскость.