Минимальная сумма модулей разности двух последовательностей

[xoxonut]

Задача:
Даны две неубывающие последовательности \{x_i\}^n_{i=1}, \{y_i\}^n_{i=1}
Дана биекция \sigma: \{1, ..., n\} \to \{1, ..., n\}, перестановка в общем.
Нужно доказать, что \forall \sigma \sum^n_{i=1} |x_i - y_i| \leqslant \sum^n_{i=1} |x_i - y_{\sigma(i)}|.

Для случая, где пара элементов меняется местами, все понятно. Где независимые пары меняются тоже понятно.
Но вот если перестановка такая, типа циклическая, непонятно) Например три элемента перетасованы. Здесь к случаю из двух как-то не особо сводится.
Индукцию не вижу как применить.
Геометрически если думать, почему-то длина отрезков больше становится, как-то так выходит, что при перестановке появляется покрывающий другие отрезок.
Совсем не знаю, как решать.

[mihaild]

xoxonut в сообщении #1693616 писал(а):

Для случая, где пара элементов меняется местами, все понятно

А к этому случаю всё сводится.
Рассмотрите $i < j$ такие что $\sigma(i) > \sigma(j)$. И посмотрите, что будет с суммой, если домножить $\sigma$ на транспозицию $(\sigma(i)\sigma(j))$.

[TOTAL]

Пошагово упорядочивайте переставленную последовательность:
$ |x_3 - y_8|+ |x_4 - y_5| \geq|x_3 - y_5|+ |x_4 - y_8|$

[Евгений Машеров]

Любая перестановка может быть выражена через последовательность парных перестановок, иначе алгоритмы сортировки не работали бы.
Положим для простоты, что последовательность иксов упорядочена по возрастанию.
Находим пару $(x_i, y_i), (x_j, y_j)$ такую, что $x_i<x_j$ и $y_i>y_j$ (или обратное соотношение). И меняем местами игреки. Наша целевая функция уменьшается. И только когда игреки будут также упорядочены по возрастанию, улучшить ЦФ не удастся.

[xoxonut]

mihaild
Ага, увеличивается сумма при "неправильной" индексации. В том плане, что изменение индексов с возрастающей пары на убывающую увеличивает сумму. Но как-то для меня было не очевидно, что изменение наоборот не сделает ее ниже изначальной. Сейчас понимаю, что противоречие получится, спасибо.

-- 08.07.2025, 21:08 --

Евгений Машеров
Для пар наверное другое соотношение, ведь все игреки могут лежать вне промежутка значений икса, слева или справа только.

[Евгений Машеров]

Прошу прощения, исправил описку.