Транснеравенство: как выгодно соединять два упорядоченных набора

Транснеравенство, или неравенство о перестановках, сравнивает суммы попарных произведений двух упорядоченных наборов. Наибольшая сумма получается при одинаковом порядке, наименьшая — при противоположном. Важно упорядочить оба набора и менять только соответствие между ними, сохраняя состав чисел.

Главная идея на двух парах

Пусть a≥b и x≥y. Сравним ax+by и ay+bx. Разность равна (a−b)(x−y), а оба множителя неотрицательны. Значит, ax+by≥ay+bx. Большому числу выгодно сопоставить большое, если цель — максимизировать сумму произведений.

Это рассуждение работает и с отрицательными числами: нужны именно порядковые отношения, а не предположение, что все числа положительны. Зато если одновременно меняются сами наборы, сравнение уже выходит за рамки этого утверждения.

Переход к нескольким числам

Для x₁≤…≤xₙ и y₁≤…≤yₙ сумма x₁y₁+…+xₙyₙ максимальна среди всех перестановок второго набора. Если в другом расположении есть неправильная соседняя пара, обмен не уменьшит сумму по доказанному двухэлементному случаю. Последовательно устраняя такие пары, придём к одинаковому порядку.

Для минимума второй набор располагают в обратном порядке. Доказательство аналогично: каждый обмен, приближающий к противоположному порядку, не увеличивает сумму. Равенство может возникать не только при буквально одинаковой перестановке, если в наборах есть совпадающие значения.

Численный пример

Наборы 1,3,5 и 2,4,6. Максимальная сумма:1·2+3·4+5·6=44. Минимальная:1·6+3·4+5·2=28. Перестановка 4,2,6 даёт 4+6+30=40, что действительно лежит между границами.

Не пытайтесь применять результат к сумме отдельных чисел: при любой перестановке её значение вообще не меняется. Смысл задачи возникает из попарного взаимодействия через произведение. Также не заменяйте доказательство правилом «так всегда кажется больше» — разность двух вариантов показывает точную причину.

Задания и ответы

1. Максимизируйте сумму произведений наборов 2,7 и 3,8. Ответ:2·3+7·8=62. Минимум 2·8+7·3=37. 2. Нужна ли положительность в доказательстве для двух упорядоченных пар? Нет. 3. Может ли разность двух перестановок равняться нулю? Да, например, если a=b или x=y.

Для закрепления возьмите три числа, одно из которых отрицательное, и перечислите все шесть соответствий второму набору. Сравните результат с теоремой. Такой опыт проверяет понимание условий и показывает, почему порядок — более важное понятие, чем простой признак «положительное число».

Ещё один разбор с отрицательными числами

Пусть первый набор равен −2, 1, 3, второй — −1, 0, 4. Одинаковый порядок даёт 2+0+12=14. Противоположный порядок даёт −8+0−3=−11. Для промежуточного расположения 0, −1, 4 сумма равна 0−1+12=11. Она находится между найденными границами. Отрицательные элементы не нарушают теорему: в доказательстве существенны не знаки самих чисел, а неотрицательность разностей соседних упорядоченных элементов. Перед вычислением подпишите оба набора целиком — иначе легко незаметно использовать одно число дважды.

Связанные материалы

Что такое линейное неравенство, Размещения, перестановки и сочетания.