Индукцией по  m + n  докажем более общее утверждение: будем считать, что в каждом столбце подчёркивается не менее k, а в каждой строке – не менее l наибольших чисел.

  База. При  m = n = k = l = 1  утверждение очевидно.

  Шаг индукции. Если в таблице m×n все подчёркнутые числа подчёркнуты дважды, то их количество не меньше kn.

  В противном случае среди чисел, подчёркнутых по одному разу, выберем наибольшее число A. Пусть оно является одним из наибольших в своём столбце (если оно наибольшее в своей строке, рассуждения аналогичны). Тогда, поскольку A не является одним из наибольших в своей строке и A – наибольшее среди всех по одному разу подчёркнутых чисел, все подчёркнутые (по строке!) наибольшие числа, стоящие в одной строке с A, подчёркнуты дважды. Выбросив эту строку, мы получим таблицу  (m−1)×n,  в которой подчёркнуто не менее l наибольших чисел в каждой строке и не менее  k − 1  числа – в каждом столбце. По предположению индукции в этой таблице дважды подчёркнуто не меньше  (k − 1)l  чисел. Эти же числа подчёркнуты дважды и в исходной таблице m×n, в которой, кроме того, дважды подчёркнуты не менее l чисел в выброшенной строке Так что всего в исходной таблице дважды подчёркнуто не меньше  (k − 1)l + l = kl  чисел.

Ответ задачи отсутствует