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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Нехай

x_1 \leq \cdots \leq x_n\quad \quad y_1 \leq \cdots \leq y_nдійсні числа
x_{\sigma (1)}, \dots ,x_{\sigma (n)}перестановка чисел x_1, \dots , x_n.

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

x_1y_1 + \cdots + x_ny_n \geq x_{\sigma (1)}y_1 + \cdots + x_{\sigma (n)}y_n \geq x_ny_1 + \cdots + x_1y_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
\qquad\text{and}\qquad
j=\sigma(k)<\sigma(j)\Rightarrow x_j\le x_{\sigma(j)}.\quad(1)

Тому,

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

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

x_{\sigma(j)}y_j+x_jy_k\le x_jy_j+x_{\sigma(j)}y_k\,, \quad(3)

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

\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, і також є максимальною. Це суперечить вибору σ.

Якщо

x_1<\cdots<x_n\quad\quad y_1<\cdots<y_n,

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

Див. також[ред.ред. код]

Посилання[ред.ред. код]