Мы будем решать задачу по индукции в несколько более общей формулировке, предполагая, что в каждом столбце подчёркивается не менее $k$ наибольших, а в каждой строке — не менее $l$ наибольших чисел. Индукцию проведём по $m+n$.
При $m=n=k=l=1$ утверждение очевидно. Пусть у нac есть таблица размерами $m\times n$. Сведём задачу к таблице $m\times (n-1)$ или $(m-1)\times n$. Если в таблице все подчёркнутые числа подчёркнуты дважды, то их количество не меньше $kn$. В противном случае среди чисел, подчёркнутых по одному разу, выберем наибольшее число $A$. Число $A$ является либо одним из наибольших в своём столбце, либо одним из наибольших в своей строке. Предположим, что $A$ — одно из наибольших в своём столбце. Тогда, поскольку $A$ не является одним из наибольших в своей строке и $A$ — наибольшее среди всех по одному разу подчёркнутых чисел, все подчёркнутые (по строке!) наибольшие числа, стоящие в одной строке с $A$, подчёркнуты дважды (см. рис. 1). Выбросив из нашей таблицы эту строку, мы получим таблицу $(m-1)\times n$, в которой подчёркнуто не менее $l$ наибольших чисел в каждой строке и не менее $k-1$ чисел — в каждом столбце. Предположение индукции заключается в том, что в этой меньшей таблице дважды подчёркнуто не меньше $(k-1)l$ чисел. Эти же числа подчёркнуты дважды и в большой таблице $m\times n$, в которой, кроме того, дважды подчёркнуты не менее $l$ чисел в выброшенной строке. Так что всего в исходной таблице дважды подчёркнуто не меньше $(k-1)l+l=kl$ чисел, что и утверждалось в задаче.
Рисунок номер 1
