Разделы 
Дополнительно
Задача по математике - 1944
2019-01-22 
Клетки таблицы $100 \times 100$ окрашены в 4 цвета так, что в любой строке и в любом столбце ровно по 25 клеток каждого цвета. Докажите, что найдутся две строки и два столбца, все четыре клетки на пересечении которых окрашены в разные цвета.
Решение:
Предположим противное: пусть среди четырех клеток на пересечении любых двух строк и любых двух столбцов есть две клетки одинакового цвета. Для удобства будем нумеровать цвета числами от 1 до 4. Назовем горизонтальной (вертикальной) парой две клетки разного цвета, лежащие в одной строке (одном столбце). Назовем горизонтальным (вертикальным) совпадением две клетки одинакового цвета, лежащие в одной строке (одном столбце). Разделим пары на 6 типов по цветам входящих в них клеток: $\{1,2\}, \{1, 3\}, \{1,4\}, \{2, 3\}, \{2,4\}, \{3,4\}$.
Рассмотрим две произвольные строчки. Докажем, что существует не менее 25 вертикальных совпадений, лежащих в этих строчках. Из сделанного предположения следует, что любые две вертикальных пары с клетками в этих строчках должны иметь общий цвет. Легко заметить, что тогда в двух рассматриваемых строчках могут быть вертикальные пары не более, чем трех типов, причем возможны только два принципиально различных случая: все пары содержат один и тот же цвет (скажем, 1) или есть пары типов $\{1,2\}, \{1,3\}$ и $\{2, 3\}$(или точно так же с другой тройкой цветов). Рассмотрим эти два случая.
Если все пары в наших двух строчках содержат клетку цвета 1, то всего пар не более, чем клеток цвета 1 в обеих строчках, т. е., не более 50. Значит, в рассматриваемых двух строчках не менее 50 совпадений.
Пусть есть пары типов $\{1, 2\}, \{1,3\}$ и $\{2, 3 \}$. В этом случае все клетки цвета 4 в наших строчках совпадают, и таким образом есть не менее 25 совпадений.
Итак, мы доказали, что в любой паре строчек не менее 25 вертикальных совпадений, аналогичный результат верен и для любой пары столбцов. Таким образом, всего в нашем квадрате есть не менее $2 \cdot \frac{99 \cdot 100}{2} \cdot 25 = 25 \cdot 99 \cdot 100$ совпадений. Но так как в любой строке и в любом столбце по 25 клеток каждого цвета, количество совпадений равно $200 \cdot \frac{25 \cdot 24}{2} \cdot 4 = 24 \cdot 100^2$. Учитывая, что $25 \cdot 99 > 24 \cdot 100$, мы приходим к противоречию. Следовательно, есть две строки и два столбца, все клетки на пересечении которых окрашены в разные цвета.
Клетки таблицы $100 \times 100$ окрашены в 4 цвета так, что в любой строке и в любом столбце ровно по 25 клеток каждого цвета. Докажите, что найдутся две строки и два столбца, все четыре клетки на пересечении которых окрашены в разные цвета.
Решение:
Предположим противное: пусть среди четырех клеток на пересечении любых двух строк и любых двух столбцов есть две клетки одинакового цвета. Для удобства будем нумеровать цвета числами от 1 до 4. Назовем горизонтальной (вертикальной) парой две клетки разного цвета, лежащие в одной строке (одном столбце). Назовем горизонтальным (вертикальным) совпадением две клетки одинакового цвета, лежащие в одной строке (одном столбце). Разделим пары на 6 типов по цветам входящих в них клеток: $\{1,2\}, \{1, 3\}, \{1,4\}, \{2, 3\}, \{2,4\}, \{3,4\}$.
Рассмотрим две произвольные строчки. Докажем, что существует не менее 25 вертикальных совпадений, лежащих в этих строчках. Из сделанного предположения следует, что любые две вертикальных пары с клетками в этих строчках должны иметь общий цвет. Легко заметить, что тогда в двух рассматриваемых строчках могут быть вертикальные пары не более, чем трех типов, причем возможны только два принципиально различных случая: все пары содержат один и тот же цвет (скажем, 1) или есть пары типов $\{1,2\}, \{1,3\}$ и $\{2, 3\}$(или точно так же с другой тройкой цветов). Рассмотрим эти два случая.
Если все пары в наших двух строчках содержат клетку цвета 1, то всего пар не более, чем клеток цвета 1 в обеих строчках, т. е., не более 50. Значит, в рассматриваемых двух строчках не менее 50 совпадений.
Пусть есть пары типов $\{1, 2\}, \{1,3\}$ и $\{2, 3 \}$. В этом случае все клетки цвета 4 в наших строчках совпадают, и таким образом есть не менее 25 совпадений.
Итак, мы доказали, что в любой паре строчек не менее 25 вертикальных совпадений, аналогичный результат верен и для любой пары столбцов. Таким образом, всего в нашем квадрате есть не менее $2 \cdot \frac{99 \cdot 100}{2} \cdot 25 = 25 \cdot 99 \cdot 100$ совпадений. Но так как в любой строке и в любом столбце по 25 клеток каждого цвета, количество совпадений равно $200 \cdot \frac{25 \cdot 24}{2} \cdot 4 = 24 \cdot 100^2$. Учитывая, что $25 \cdot 99 > 24 \cdot 100$, мы приходим к противоречию. Следовательно, есть две строки и два столбца, все клетки на пересечении которых окрашены в разные цвета.
