|
|
 |
Условие
В прямоугольную таблицу из m строк и n столбцов записаны mn положительных чисел. Найдём в каждом столбце произведение чисел и сложим все n таких произведений. Докажите, что если переставить числа в каждой строке в порядке возрастания, то сумма аналогичных произведений будет не меньше, чем в первоначальной. Решите эту задачу для
а) m = n = 2;
б) m = 2 и произвольного n;
в) любых натуральных m и n.
Решение
в) Индукция по числу столбцов таблицы. База (один столбец) очевидна.
Шаг индукции. Обозначим через Pi произведение чисел в i-м столбце. Переставим теперь столбцы так (это не изменит сумму произведений), чтобы произведение P1 стало минимальным. Обозначим через xij число, стоящее в i-й строке и
j-м столбце. Предположим, что xi1 – не минимальное число в i-й строке: минимальным является xik. Поменяем местами xi1 и xik и проверим, что сумма произведений при этом возрастёт. Обозначим через П1 произведение всех чисел в первом столбце, кроме xi1, через Пk – произведение всех чисел в k-м столбце, кроме xik. Разность новой и старой сумм равна xi1Пk + xikП1 – xi1П1 – xikПk = (xi1 – xik)(Пk – П1). Эта величина положительна, так как xi1 > xik и Пk > П1, поскольку xikПk ≥ xi1П1. Значит, после
перестановки сумма увеличилась. Кроме того, произведение новых чисел в первом столбце по-прежнему минимально. Таким образом, мы можем переставить все числа,
минимальные в строках, в первый столбец, и сумма произведений увеличится.
Если упорядочить строки в таблице, образованной столбцами со 2-го по n-й, то мы получим исходную таблицу с упорядоченными строками. По предположению индукции при этом упорядочении сумма произведений P2 + ... + Pn не уменьшится. Следовательно, сумма P1 + ... + Pn в первоначальной таблице не больше, чем аналогичная сумма в таблице с упорядоченными строками.
Замечания
1. Заметим, что при перемене мест чисел, которую мы производим, сумма произведений строго увеличивается. Отсюда следует, что сумма произведений равна максимальной в том и только в том случае, когда таблица получается из таблицы с упорядоченными строками путем перестановки столбцов.
2. Если не предполагать, что в таблице стоят положительные числа, то утверждение неверно. Простейшим примером служит следующая таблица 2×3.
