Республиканская олимпиада по математике, 2026 год, 10 класс

Рассмотрим клетчатую доску $n \times n$. Две клетки называются соседними, если у них есть общая сторона. Множество клеток называется связным, если из любой клетки множества можно дойти до любой другой, не выходя за пределы этого множества и двигаясь по соседним клеткам. Существует ли натуральное число $n$, для которого можно покрасить все клетки доски $n\times n$ в три цвета так, чтобы все цвета встречались, не было двух одноцветных соседних клеток и все клетки любых двух цветов составляли связное множество клеток? ( Уразгулов А. )

Комментарий/решение

Такого натурального числа $n$ не существует.

Рассмотрим доску размером $n \times n$ и введем для нее классическую шахматную раскраску. Множество всех клеток разобьется на два непересекающихся множества $B$ и $W$ где $B$ это черные клетки а $W$ это белые клетки. Любые две соседние клетки всегда принадлежат разным множествам. Предположим что существует раскраска всех клеток в три цвета $c_1$ $c_2$ и $c_3$ удовлетворяющая всем условиям. Рассмотрим множество клеток $S_{12}$ окрашенных только в цвета $c_1$ и $c_2$. По условию это множество связно и в нем нет соседних клеток одного цвета. Значит $S_{12}$ является связным двудольным графом. Любой путь внутри $S_{12}$ строго чередует цвета $c_1$ и $c_2$. В силу свойств связного двудольного графа все клетки цвета $c_1$ должны принадлежать строго одному из множеств $B$ или $W$. Пусть все клетки цвета $c_1$ принадлежат множеству $B$. Тогда все клетки цвета $c_2$ обязаны принадлежать множеству $W$. Теперь рассмотрим связное множество $S_{23}$ состоящее из клеток цветов $c_2$ и $c_3$. Так как мы уже определили что все клетки цвета $c_2$ лежат в множестве $W$ то все клетки цвета $c_3$ в силу аналогичного чередования обязаны лежать в множестве $B$. Наконец рассмотрим множество $S_{13}$ образованное клетками цветов $c_1$ и $c_3$. Мы получили что все клетки цвета $c_1$ лежат в $B$ и все клетки цвета $c_3$ также лежат в $B$. Следовательно в множестве $S_{13}$ вообще нет клеток из множества $W$. Это означает что в $S_{13}$ нет ни одной пары соседних клеток так как соседом клетки из $B$ может быть только клетка из $W$. По условию каждый цвет обязательно присутствует на доске поэтому в $S_{13}$ есть хотя бы одна клетка цвета $c_1$ и хотя бы одна клетка цвета $c_3$. Множество состоящее из нескольких абсолютно изолированных друг от друга клеток никак не может быть связным. Мы получили прямое противоречие. Следовательно требуемая раскраска доски невозможна.