В некоторых клетках прямоугольной таблицы из $n$ строк и $m\gt n$ столбцов расставлены звёздочки так, что в каждом столбце стоит хотя бы одна звёздочка. Докажите, что найдётся такая звёздочка, что в её строке звёздочек больше, чем в её столбце.
Из исходной таблицы $A$ со звёздочками построим две новые таблицы — «красную» и «голубую», в которых звёздочки заменены числами: в красной таблице эти числа равны $\dfrac1k$, где $k$ — количество звёздочек в соответствующем столбце, а в голубой эти числа равны $\dfrac1l$, где $l$ — количество звёздочек в соответствующей строке. Тогда сумма всех красных чисел равна $m$ — числу столбцов (в каждом столбце сумма равна 1), а сумма всех голубых чисел не больше $n$ — числа строк (в каждой строке сумма равна 0 или 1). Поскольку $m\gt n$, то найдётся звёздочка такая, что соответствующее красное число $\dfrac1k$ больше голубого числа $\dfrac1l$: $\dfrac1k\gt\dfrac1l$, откуда $k\lt l$, т. е. для этой звёздочки выполнено требуемое условие.
Точно так же можно доказать и более сильное утверждение: в условиях задачи найдётся звёздочка, для которой отношение числа звёздочек в её строке и в её столбце не меньше $\dfrac mn$.
Задача имеет и совершенно другие решения (в частности, по индукции), но приведённое — одно из самых простых.
