Решите задачу: Клетчатая доска размером n × n покрашена в зелёный, синий и белый цвета. Напиши такое наименьшее n, для которого при любой раскраске найдутся строка и столбец по крайней мере с тремя клетками одного цвета.

Для решения этой задачи применим принцип Дирихле. Предположим, что у нас есть доска $n \times n$, где $n$ - наименьшее число, для которого обязательно найдется строка и столбец с тремя клетками одного цвета. Рассмотрим каждую строку. В каждой строке может быть любое сочетание зеленого, синего и белого цвета. Нам нужно найти такое $n$, чтобы в любом случае нашлась строка и столбец, в которых есть хотя бы три клетки одного цвета. Допустим, что в каждой строке нет трех клеток одного цвета. Тогда количество клеток каждого цвета в строке не превышает 2. Количество различных комбинаций цветов в строке длины $n$ равно $3^n$. Если мы имеем $n$ строк, и в каждой строке не больше двух клеток одного цвета, то при достаточно большом $n$ у нас обязательно найдется строка, которая совпадает с каким-то столбцом, и тогда у нас будет хотя бы три клетки одного цвета. Давайте рассмотрим случай, когда $n = 7$. Если в каждой строке нет трех клеток одного цвета, это означает, что в каждой строке каждого цвета не больше двух клеток. Но при $n = 7$ это не гарантирует, что в каком-то столбце не будет трех клеток одного цвета. Если $n = 3$, то строка может выглядеть как "зеленый, синий, белый". Но тогда может не найтись столбца с тремя клетками одного цвета. Предположим, что $n = 5$. Тогда строка может выглядеть как "зеленый, зеленый, синий, синий, белый". Опять же, может не найтись столбца с тремя клетками одного цвета. Если $n = 9$, то в каждой строке должно быть не более двух клеток каждого цвета. Значит, в строке 9 клеток, и цветов 3, поэтому 9 / 3 = 3. То есть в среднем в каждой строке по 3 клетки каждого цвета. Но нам нужно, чтобы было не более 2 клеток каждого цвета, чтобы не было строки и столбца с тремя клетками одного цвета. Рассмотрим такой случай. Пусть $n=7$. Раскрасим клетки доски так, чтобы в каждой строке было не более двух клеток каждого цвета. Это возможно. Но тогда при достаточно большом количестве строк (а их $n$) обязательно найдется столбец, где будет хотя бы три клетки одного цвета. Если в каждой строке у нас не более двух клеток одного цвета, то получается, что у нас должно быть хотя бы 3 строки, чтобы образовался столбец с тремя клетками одного цвета. Рассмотрим случай $n=7$. Предположим, что в каждой строке не больше двух клеток каждого цвета. Тогда общее количество клеток каждого цвета не больше $2n = 14$. Если в каждом столбце не больше двух клеток каждого цвета, то общее количество клеток каждого цвета не больше $2n = 14$. Но всего клеток $n^2 = 49$. Получается, что $3 imes 14 = 42 < 49$. Итак, ищем такое минимальное $n$, чтобы выполнялось условие задачи. Если $n=7$, то у нас получается, что в любом случае найдется строка или столбец с тремя клетками одного цвета. Ответ: 7