Республиканская олимпиада по математике, 2007 год, 10 класс

Каждая клетка доски $100\times 100$ покрашена в один из 100 цветов так, что имеется ровно 100 клеток каждого цвета. Докажите, что существует строка или столбец, в котором встречаются клетки не менее 10 различных цветов.

Комментарий/решение

Введем несколько переменных: $S_{i}$ это множество всех точек цвета $i, 1 \leq i \leq 100$. $P_{i}$ это множество всех проекций, то есть индексы строк и столбцов в которых есть клетки цветы $i$, тогда $\star P_{i}$ будет размер множества $P_{i}$ - то есть сумма количества индексов строк и столбцов где есть клетки цвета $i$. Рассмотрим какой-нибудь цвет $j$, и пусть клетки этого цвета есть в $n$ строках и $m$ столбцах. Тогда $\star P_{i} = m+n$, а $100 \leq m*n$ так если рассмотреть все строки и столбцы где есть эти клетки и составить прямоугольник с размерами $m*n$, то все клетки цвета $j$ войдут в этот прямоугольник, и даже могут остаться лишние клетки. Тогда: $$100 \leq m*n \leq \left(\frac{m + n}{2}\right)^2 = \frac{(\star P_{j})^2}{4}$$ Откуда $\star P_{j} \geq 20$. То есть каждый цвет присутствует по крайней в $20$ различных столбцах и строках. Тогда $\sum \limits_{i=1}^{100}{\star P_{i}} \geq 20 * 100 =2000$. С другой стороны эта сумма равна сумме количества различных цветов в каждой строке и столбце. Если пойти от противного и предположить что в каждой строке и столбце клетки покрашены в не более чем $9$ различных цветов то всего эта сумма не более чем $\sum \limits_{i=1}^{100}{\star P_{i}} \leq 9 * 200 =1800$, но $2000 > 1800$, противоречие. Значит найдется строка или столбец в котором клетки покрашены не менее чем в $10$ различных цветов.