Разделы 
Дополнительно
Задача по математике - 1660
2019-01-20 
Каждая клетка клетчатой плоскости раскрашена в один из $n^2$ цветов так, что в любом квадрате из $n \times n$ клеток встречаются все цвета. Известно, что в какой-то строке встречаются все цвета. Докажите, что существует столбец, раскрашенный ровно в $n$ цветов.
Решение:
Назовем одну из строк, в которой встречаются все цвета, выделенной. Назовем множество клеток, отстоящих друг от друга по горизонтали и вертикали на кратное п число клеток, полным.
Лемма. В полном множестве либо каждая строка, либо каждый столбец одноцветны.
Доказательство. Предположим, что в какой-то строке нашего множества нашлись две клетки разного цвета; тогда найдутся и две клетки разного цвета на расстоянии $n$. Пусть эти клетки $a$ и $b$, а клетки полного множества над ними - $x$ и $у$ (см. рис.). Из сравнения цветов в квадратах, составленных из клеток множеств $a \cup S_1 \cup D$ и $x \cup S_2 \cup D$ видно, что наборы цветов в множествах $a \cup S_1$ и $x \cup S_2$ одинаковы; аналогично, одинаковы наборы цветов в $S_2 \cup y$ и $S_1 \cup b$. Тогда в множестве $S_1$ нет клеток цвета $b$, поэтому и в множестве $x \cup S_2$ нет такого цвета; однако в $S_2 \cup y$ он есть, поэтому цвета $y$ и $b$ совпадают; аналогично совпадают цвета $x$ и $a$. Повторяя эти рассуждения, получаем, что столбец нашего множества, содержащий $a$, окрашен одинаково, и то же со столбцом $b$. Теперь, если найдутся две клетки на расстоянии $n$ в каком-то столбце, покрашенные по-разному, то строки множества, их содержащие, будут одноцветными. Но они будут пересекаться со столбцом цвета $b$, и поэтому их цвета будут совпадать, что невозможно. Полученное противоречие доказывает лемму.
Назовем полное множество вертикальным, если любой его столбец одноцветен, и горизонтальным в противном случае. Докажем, что все горизонтальные полные множества пересекаются с выделенной строкой. Пусть это не так. Рассмотрим строку нашего множества, ближайшую к выделенной; пусть она имеет цвет $a$. Тогда любую клетку выделенной строки можно заключить в квадрат вместе с какой-то клеткой цвета a из нашего горизонтального множества; поэтому в выделенной строке нет цвета $a$. Противоречие.
Теперь легко завершить доказательство требуемого. Заметим, что если есть столбец, для которого все полные множества, его содержащие, вертикальны, то в этом столбце ровно $n$ цветов, так как его раскраска периодична с периодом $n$. Пусть любой столбец пересекается с горизонтальным полным множеством. Тогда выделенная строка пересекается с $n$ горизонтальными множествами, строки которых одноцветны; поэтому в выделенной строке только n цветов. Противоречие, доказывающее требуемое.
Замечание 1. Можно доказать даже, что в любом столбце содержится ровно $n$ цветов.
Замечание 2. Утверждение задачи (но не предыдущего замечания!) остается верным, если в какой-то строке содержится хотя бы $n^2 - n + 1$ цвет.
Каждая клетка клетчатой плоскости раскрашена в один из $n^2$ цветов так, что в любом квадрате из $n \times n$ клеток встречаются все цвета. Известно, что в какой-то строке встречаются все цвета. Докажите, что существует столбец, раскрашенный ровно в $n$ цветов.
Решение:
Назовем одну из строк, в которой встречаются все цвета, выделенной. Назовем множество клеток, отстоящих друг от друга по горизонтали и вертикали на кратное п число клеток, полным.
Лемма. В полном множестве либо каждая строка, либо каждый столбец одноцветны.
Доказательство. Предположим, что в какой-то строке нашего множества нашлись две клетки разного цвета; тогда найдутся и две клетки разного цвета на расстоянии $n$. Пусть эти клетки $a$ и $b$, а клетки полного множества над ними - $x$ и $у$ (см. рис.). Из сравнения цветов в квадратах, составленных из клеток множеств $a \cup S_1 \cup D$ и $x \cup S_2 \cup D$ видно, что наборы цветов в множествах $a \cup S_1$ и $x \cup S_2$ одинаковы; аналогично, одинаковы наборы цветов в $S_2 \cup y$ и $S_1 \cup b$. Тогда в множестве $S_1$ нет клеток цвета $b$, поэтому и в множестве $x \cup S_2$ нет такого цвета; однако в $S_2 \cup y$ он есть, поэтому цвета $y$ и $b$ совпадают; аналогично совпадают цвета $x$ и $a$. Повторяя эти рассуждения, получаем, что столбец нашего множества, содержащий $a$, окрашен одинаково, и то же со столбцом $b$. Теперь, если найдутся две клетки на расстоянии $n$ в каком-то столбце, покрашенные по-разному, то строки множества, их содержащие, будут одноцветными. Но они будут пересекаться со столбцом цвета $b$, и поэтому их цвета будут совпадать, что невозможно. Полученное противоречие доказывает лемму.
Назовем полное множество вертикальным, если любой его столбец одноцветен, и горизонтальным в противном случае. Докажем, что все горизонтальные полные множества пересекаются с выделенной строкой. Пусть это не так. Рассмотрим строку нашего множества, ближайшую к выделенной; пусть она имеет цвет $a$. Тогда любую клетку выделенной строки можно заключить в квадрат вместе с какой-то клеткой цвета a из нашего горизонтального множества; поэтому в выделенной строке нет цвета $a$. Противоречие.
Теперь легко завершить доказательство требуемого. Заметим, что если есть столбец, для которого все полные множества, его содержащие, вертикальны, то в этом столбце ровно $n$ цветов, так как его раскраска периодична с периодом $n$. Пусть любой столбец пересекается с горизонтальным полным множеством. Тогда выделенная строка пересекается с $n$ горизонтальными множествами, строки которых одноцветны; поэтому в выделенной строке только n цветов. Противоречие, доказывающее требуемое.
Замечание 1. Можно доказать даже, что в любом столбце содержится ровно $n$ цветов.
Замечание 2. Утверждение задачи (но не предыдущего замечания!) остается верным, если в какой-то строке содержится хотя бы $n^2 - n + 1$ цвет.
