Задача
а) Прямоугольная таблица из m строк и n столбцов заполнена числами. Переставим числа в каждой строке в порядке возрастания. Если после этого переставить числа в каждом столбце в порядке возрастания, то в каждой строке они по-прежнему будут стоять в порядке возрастания. Докажите это.
б) Что будет, если действовать в другом порядке: в первоначальной таблице сначала переставить числа по возрастанию в столбцах, а потом – в строках: получится ли в результате та же самая таблица, что и в первом случае, или другая?
Решение
а) Рассмотрим таблицу, у которой в каждой строке числа стоят в порядке возрастания.
Докажем, что k-е по величине (считая от наибольшего) число bk в r-м столбце не меньше k-го числа ak в l-м столбце. Действительно, в l-м столбце имеется k чисел, не меньших ak. В тех же строках в r-м столбце имеется k чисел, не меньших ak. Поэтому ak ≤ bk.
Отсюда и следует утверждение задачи. б) Пример см. на рисунке.
Ответ
б) Вообще говоря, другая.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь