Олимпиадная задача по комбинаторике и принципу Дирихле для 8-11 классов

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

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

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

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

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

  Итак, мы доказали, что в каждой паре строчек не менее 25 вертикальных совпадений; аналогичный результат верен и для любой пары столбцов. Таким образом, всего в нашем квадрате есть не менее 25·100·99 совпадений. Но так как в каждой строке и в каждом столбце по 25 клеток каждого цвета, количество совпадений равно  100·25·24·4 = 24·100².  Учитывая, что  25·99 > 24·100,  приходим к противоречию.

Ответ задачи отсутствует