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

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

${\displaystyle -x_{n}\leq \cdots \leq -x_{1}.}$

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

${\displaystyle 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. Оскільки

${\displaystyle j<k\Rightarrow y_{j}\leq y_{k}\qquad {\text{and}}\qquad j=\sigma (k)<\sigma (j)\Rightarrow x_{j}\leq x_{\sigma (j)}.\quad (1)}$

Тому,

${\displaystyle 0\leq (x_{\sigma (j)}-x_{j})(y_{k}-y_{j}).\quad (2)}$

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

${\displaystyle x_{\sigma (j)}y_{j}+x_{j}y_{k}\leq x_{j}y_{j}+x_{\sigma (j)}y_{k}\,,\quad (3)}$

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

${\displaystyle \tau (i):={\begin{cases}i&i\in \{1,\ldots ,j\},\\\sigma (j)&i=k,\\\sigma (i)&i\in \{j+1,\ldots ,n\}\setminus \{k\},\end{cases}}}$

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

Якщо

${\displaystyle x_{1}<\cdots <x_{n}\quad \quad y_{1}<\cdots <y_{n},}$

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

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

• Доведення нерівності перестановок на PlanetMath.(англ.)