Нерівність перестановок

Нехай

$x_1\le \cdots \le x_n{y}_1\le \cdots \le y_n$ — дійсні числа

$x_{\sigma (1)},\dots ,x_{\sigma (n)}$ — перестановка чисел $x_1,\dots ,x_n$.

Тоді справедливою є нерівність:

$x_1{y}_1+\cdots +x_n{y}_n\ge x_{\sigma (1)}{y}_1+\cdots +x_{\sigma (n)}{y}_n\ge x_n{y}_1+\cdots +x_1{y}_n.$

Доведення

Друга нерівність випливає з першої, якщо її застосувати до послідовності

$-x_n\le \cdots \le -x_1.$

Тому достатньо довести лише першу нерівність. Оскільки кількість перестановок є скінченною, принаймні для одної значення суми

$x_{\sigma (1)}{y}_1+\cdots +x_{\sigma (n)}{y}_n$

є максимальним. Якщо таких перестановок є кілька нехай σ — та з них, що залишає незмінними найбільшу кількість чисел.

Доведемо, що σ — одинична перестановка. Припустимо, що це не так. Тоді існує число j ∈ {1, ..., n − 1}, таке що σ(j) ≠ j і σ(i) = i для всіх i ∈ {1, ..., j − 1}. Тому σ(j) > j і існує k ∈ {j + 1, ..., n} для якого σ(k) = j. Оскільки

$j<k\Rightarrow y_j\le y_k\text{and}j=\sigma (k)<\sigma (j)\Rightarrow x_j\le x_{\sigma (j)}.(1)$

Тому,

$0\le (x_{\sigma (j)}-x_j)(y_k-y_j).(2)$

Розписуючи добуток отримуємо:

$x_{\sigma (j)}{y}_j+x_j{y}_k\le x_j{y}_j+x_{\sigma (j)}{y}_k,(3)$

тому перестановка

$\tau (i):=\{\begin{array}{cc}i& i\in \{1,\dots ,j\},\\ \sigma (j)& i=k,\\ \sigma (i)& i\in \{j+1,\dots ,n\}\setminus \{k\},\end{array}$

що утворюється з σ заміною значень σ(j) і σ(k), має принаймні одну додаткову фіксовану точку j, і також є максимальною. Це суперечить вибору σ.

Якщо

$x_1<\cdots <x_n{y}_1<\cdots <y_n,$

то нерівності (1), (2), і (3) є строгими, тому максимум може бути досягнутим лише в одиничній перестановці.

Див. також

• Нерівність Чебишова для сум чисел

Посилання

• Шаблон:PlanetMath