Задача: При каком наименьшем k в любой раскраске клеток таблицы 10хk в 5 цветов найдутся четыре клетки одного цвета, стоящие на пересечении двух строк и двух столбцов?
Решение: Докажем, что такое k подходит. Подсчитаем все пары клеток одного цвета, стоящих в одном столбце. В каждом столбце таких пар не менее пяти (после того, как мы возьмем по одной клетке каждого цвета, встречающегося в этом столбце, останется еще не менее n клеток, каждая из которых составляет пару с одной из взятых в начале). Поэтому всего таких пар не менее, чем 5х46, и, следовательно, существует такой цвет, что пар этого цвета не менее 46. С другой стороны, пара клеток может быть расположена в столбце высоты 10 всего 10х9/2 = 45 способами. Поэтому среди пар найденного цвета есть две, расположенные в своих столбцах одинаково. Эти две пары и составляют нужную нам четверку.
С другой стороны, при k = 45 и, следовательно, при любом меньшем k прямоугольник 10хk можно раскрасить в 5 цветов так, чтобы требуемой четвёрки не нашлось. Для этого можно раз-бить клетки каждого столбца прямоугольника 5х9 на пять пар так, чтобы пары в разных столбцах не были одинаково расположены. Тогда все способы расположения двух клеток в столбце будут использованы по разу. В каждом столбце полученные пять пар раскрасим в пять разных цветов. Затем составим прямоугольник 10хk из пяти прямоугольников 10х9, раскраски которых будут отличаться циклической перестановкой цветов. В полученном прямоугольнике две одинаково расположенные одноцветные пары всегда будут разного цвета.
Искомое разбиение на пары столбцов прямоугольника 10х9 строится так. В каждом столбце занумеруем клетки числами от 1 до 10 сверху вниз и в i-м столбце объединим в пары клетки с номерами, сумма которых сравнима с 2i по модулю 9, а i-ю клетку — с десятой. Легко видеть, что никакая пара номеров не будет объединена более чем в одном столбце.
