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

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