Подсчеты в клетчатых задачах

Предположим противное: пусть среди четырёх клеток на пересечении любых двух строк и любых двух столбцов есть две клетки одинакового цвета.

Назовём горизонтальной (вертикальной) парой две клетки разного цвета, лежащие в одной строке (одном столбце). Назовём горизонтальным (вертикальным) совпадением две клетки одинакового цвета, лежащие в одной строке (одном столбце). Разделим пары на 6 типов по цветам входящих в них клеток:

Рассмотрим две произвольные строчки. Из предположения следует, что каждые две вертикальных пары с клетками в этих строчках должны иметь общий цвет. Тогда в двух рассматриваемых строчках могут быть вертикальные пары не более, чем трех типов, причем возможны только два принципиально различных случая: все пары содержат один и тот же цвет (скажем, ) или есть пары типов и (или точно так же с другой тройкой цветов). Рассмотрим эти два случая.

Если все пары в наших двух строчках содержат клетку цвета то всего пар не более, чем клеток цвета в обеих строчках, то есть не более Значит, в рассматриваемых двух строчках не менее совпадений.

Пусть есть пары типов и В этом случае все клетки цвета в наших строчках совпадают, таким образом, есть не менее совпадений.

Итак, мы доказали, что в каждой паре строчек не менее вертикальных совпадений. Аналогичный результат верен и для любой пары столбцов. Таким образом, всего в нашем квадрате есть не менее совпадений. Но так как в каждой строке и в каждом столбце по клеток каждого цвета, количество совпадений равно Учитывая, что приходим к противоречию.