|
|
 |
Условие
Клетки таблицы 100×100 окрашены в 4 цвета так, что в каждой строке и в каждом столбце ровно по 25 клеток каждого цвета.
Докажите, что найдутся две строки и два столбца, все четыре клетки на пересечении которых окрашены в разные цвета.
Решение
Предположим противное: пусть среди четырёх клеток на пересечении любых двух строк и любых двух столбцов есть две клетки одинакового цвета.
Назовём горизонтальной (вертикальной) парой две клетки разного цвета, лежащие в одной строке (одном столбце). Назовём горизонтальным (вертикальным) совпадением две клетки одинакового цвета, лежащие в одной строке (одном столбце). Разделим пары на 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, приходим к противоречию.
