|
|
 |
Условие
Каждая клетка клетчатой плоскости раскрашена в один из n² цветов так, что в каждом квадрате из n× клеток встречаются все цвета. Известно, что в какой-то строке встречаются все цвета. Докажите, что существует столбец, раскрашенный ровно в n цветов.Решение
Назовём одну из строк, в которой встречаются все цвета, выделенной. Назовём множество клеток, отстоящих друг от друга по горизонтали и вертикали на кратное n число клеток, полным.
Лемма. В полном множестве либо каждая строка, либо каждый столбец одноцветны.
Доказательство. Предположим, что в какой-то строке нашего множества нашлись две клетки разного цвета; тогда найдутся и две клетки разного цвета на расстоянии n. Пусть это клетки a и b, а клетки полного множества над ними – x и y (см. рис.).
Из сравнения цветов в квадратах, составленных из клеток множеств
a ∪ S1 ∪ D и x ∪ S2 ∪ D, видно, что наборы цветов в множествах a ∪ S1 и x ∪ S2 одинаковы; аналогично одинаковы наборы цветов в S2 ∪ y и S1 ∪ b. Так как в множестве S1 нет клеток цвета b, то и в множестве x ∪ S2 нет такого цвета; однако в S2 ∪ y он есть, поэтому цвета y и b совпадают. Аналогично совпадают цвета x и a.
Повторяя эти рассуждения, получаем, что столбец нашего множества, содержащий a, окрашен одинаково, и то же со столбцом b.
Если найдутся две клетки на расстоянии n в каком-то столбце,
покрашенные по-разному, то аналогично докажем, что строки множества, их содержащие, будут одноцветными. Но они пересекаются со столбцом цвета b, поэтому их цвета совпадают. Противоречие.
Назовём полное множество вертикальным, если любой его столбец одноцветен, и горизонтальным в противном случае. Докажем, что все горизонтальные полные множества пересекаются с выделенной строкой.
Пусть это не так. Рассмотрим строку нашего множества, ближайшую к выделенной; пусть она имеет цвет a. Тогда каждую клетку выделенной строки можно заключить в квадрат n×n вместе с какой-то клеткой цвета a из нашего горизонтального множества; поэтому в выделенной строке нет цвета a. Противоречие.
Пусть каждый столбец пересекается с горизонтальным полным множеством. Тогда выделенная строка пересекается с n горизонтальными множествами, строки которых одноцветны; поэтому в выделенной строке только n цветов. Противоречие.
Следовательно, есть столбец, для которого все полные множества, его содержащие, вертикальны. Его раскраска периодична с периодом n, то есть в этом столбце ровно n цветов.
Замечания
1. Можно доказать даже, что в каждом столбце содержится ровно n цветов.
2. Утверждение задачи (но не предыдущего замечания!) остаётся верным, если в какой-то строке содержится хотя бы n² – n + 1 цвет.
