Математика · объяснение и практика

Как одинаковый порядок увеличивает сумму попарных произведений

Как порядок соединения двух наборов меняет сумму произведений, доказать оптимальность сортировки обменом пары и учесть равные или отрицательные значения.

Синяя и оранжевая половины складываются в целый круг.

В теме Оценки и неравенства: углубление · Учебная карта

В маршруте Неравенства и условия равенства · 10 тем

Главная мысль

Сумма попарных произведений двух действительных наборов максимальна при одинаковой сортировке и минимальна при противоположной. Переставляются только связи между фиксированными значениями.

Порядок пар влияет на сумму

Возьмём значения −2,1,4 и −3,2,5. При одинаковом возрастании сумма произведений равна 6+2+20=28. При противоположном порядке получаем −10+2−12=−20. Сами наборы и их суммы не изменились, поменялось только то, какое значение одного набора умножается на какое значение другого.

Утверждение относится и к отрицательным действительным значениям. Однако нельзя свободно менять оба набора в задаче, где пары уже заданы смыслом: например, показатель относится к определённому человеку. Неравенство сравнивает допустимые перестановки, а не разрешает создавать новые данные. Перед оптимизацией нужно удостовериться, что нужные связи действительно можно переставлять.

Исправить одну инверсию

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

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

Пример

Для наборов 1,3,8 и 2,5,9 найдите наибольшую и наименьшую сумму трёх попарных произведений.

Максимум при одинаковом порядке: 1·2+3·5+8·9=89. Минимум при обратном: 1·9+3·5+8·2=40. Обменный довод сравнивает их со всеми остальными перестановками.

Граница задачи о назначениях

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

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

От чтения к действию

А теперь — вы

Для наборов 1,4,6 и 2,3,5 какова максимальная сумма попарных произведений при свободном сопряжении?

Частые вопросы

Нужна ли положительность всех значений?

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

Когда максимум может быть достигнут несколькими порядками?

Например, при равных значениях некоторые перестановки не меняют сумму. Уникальность требует дополнительных строгих условий.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться