|
|
 |
Условие
В таблице размерами m×n расставлены числа – в каждой клетке по числу. В каждом столбце подчеркнуто k наибольших чисел (k ≤ m), в каждой строке – l наибольших чисел (l ≤ n). Докажите, что по крайней мере kl чисел подчёркнуты дважды.
Решение
Индукцией по 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 чисел.
