ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 73615
Темы:    [ Числовые таблицы и их свойства ]
[ Индукция (прочее) ]
[ Принцип крайнего (прочее) ]
Сложность: 4
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

В таблице размерами 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  чисел.

Источники и прецеденты использования

журнал
Название "Квант"
год
Год 1977
выпуск
Номер 3
Задача
Номер М435

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .