Подстановки, неравенства

[Nimza]

Помогите решить следующую задачу:

Даны две системы чисел:

\[ x_1 \leqslant x_2 \leqslant ... \leqslant x_n \]

и

\[ y_1 \leqslant y_2 \leqslant ... \leqslant y_n \]

. Доказать, что для любой подстановки

\[ \sigma \in S_n \]

выполняется неравенство

\[ \sum\limits_{i = 1}^n {\left| {x_i - y_i } \right| \leqslant } \sum\limits_{i = 1}^n {\left| {x_i - y_{\sigma (i)} } \right|} \]

.

[Brukvalub]

Начните с доказательства этого факта для транспозиций, а потом можно попробовать использовать разложение подстановки в циклы, а циклы - в произведение транспозиций.

[Профессор Снэйп]

Brukvalub писал(а):

Начните с доказательства этого факта для транспозиций, а потом можно попробовать использовать разложение подстановки в циклы, а циклы - в произведение транспозиций.

Непонятно, как работать с произведением перестановок.

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

А как для циклов доказывать?.. Надо думать. Возможно, пройдёт индукция по длине цикла, хотя не уверен.

Задачу можно смело переносить в олимпиадный раздел!

[Nimza]

Большущее спасибо за идею. Разложить на циклы, правда, не удалось, по получилось сделать вот как:

Обозначим

\[ S = \sum\limits_{i = 1}^n {\left| {x_i - y_i } \right|} \]

,

\[ S' = \sum\limits_{i = 1}^n {\left| {x_i - y_{\sigma (i)} } \right|} \]

.

Рассмотрим в суммах S и S' слагаемые, соответствующие i = 1. Допустим. что они совпали. Переходим к i = 2 и проделываем то же самое.
В случае если на k-ом шаге равенство нарушается, k-ое слагаемое суммы S' имеет вид

\[ \left| {x_k - y_l } \right| \]

, где

\[ k < l \leqslant n \]

. Тогда в сумме S' найдётся t-ое слагаемое, имеющее вид

\[ \left| {x_t - y_k } \right| \]

,

\[ k < t \leqslant n \]

.
Достаточно показать, что

\[ \left| {x_k - y_l } \right| + \left| {x{}_t - y_k } \right| \geqslant \left| {x_k - y_k } \right| + \left| {x{}_t - y_l } \right| \]

(*).

После этого рассмотрим сумму S'', полученную из S' заменой слагаемых из левой части (*) на слагаемые из правой части (*), для которой будет

\[ S' \geqslant S'' \]

и переходим к i = k+1. На n-ом шаге будем иметь

\[ S' \geqslant S'' \geqslant ... \geqslant S^{(m)} = S \]

(где m-l вроде бы есть сумма длин l независимых циклов, на которые разлагается

\[ \sigma \]

), из чего будет следовать

\[ S' \geqslant S \]

.


Для доказательства (*) отметим на числовой прямой точки

\[ A_1 (x_k ),A_2 (x_t ),B_1 (y_k ),B_2 (y_l ) \]

. Тогда каждое слагаемое слева и справа можно трактовать как длину соответствующего отрезка. Рассмотрев 6 возможных случаев взаимного расположения точек, убедимся в правоте (*)