Задача М71‍‍

Рассмотрим таблицу, у которой в каждой строке числа стоят в порядке возрастания, и докажем, что, если $l\lt r$‍,‍ то наибольшее число $r$‍‍-го столбца (обозначим его через $b$‍)‍ не меньше наибольшего числа $l$‍‍-го столбца (обозначим его через $a$‍).‍ Действительно, число, стоящее на пересечении той строки, где стоит $a$‍,‍ и $r$‍‍-го столбца, не меньше $a$‍‍ (потому что в строке числа идут в порядке возрастания).

Аналогично можно доказать, что $k$‍‍-е по величине (считая от наибольшего) число в $r$‍‍-столбце ($b_k$‍)‍ не меньше $k$‍‍-го по величине числа в $l$‍‍-м столбце ($a_k$‍)‍ Действительно (рис. 4), в $l$‍‍-м столбце имеется $k$‍‍ чисел, не меньших $a_k$‍,‍ следовательно, в тех же строках в $r$‍‍-м столбце имеется $k$‍‍ чисел, не меньших $a_k$‍,‍ поэтому $b_k\ge a_k$‍.‍ Отсюда следует, что если переставить числа по столбцам в порядке возрастания, то $k$‍‍-е число в $r$‍‍-м столбце будет не меньше $k$‍‍-го числа в $l$‍‍-м столбце для любых $l\lt r$‍,‍ т. е. что в $k$‍‍-й строке числа идут в порядке возрастания. Утверждение задачи доказано.

В зависимости от того, как переставлять числа (сначала по столбцам или сначала по строкам), могут получиться разные таблицы. Чтобы убедиться в этом, достаточно привести пример (рис. 5).

Кроме решений, близких к нашему, было прислано и много других, в которых проводится индукция; в некоторых письмах доказано, что можно осуществлять перестановки последовательно в каждом столбце так, что при этом всё время числа будут стоять по строкам в порядке возрастания.