Матеріал з Вікіпедії — вільної енциклопедії.
Нехай
x
1
≤
⋯
≤
x
n
y
1
≤
⋯
≤
y
n
{\displaystyle x_{1}\leq \cdots \leq x_{n}\quad \quad y_{1}\leq \cdots \leq y_{n}}
дійсні числа
x
σ
(
1
)
,
…
,
x
σ
(
n
)
{\displaystyle x_{\sigma (1)},\dots ,x_{\sigma (n)}}
перестановка чисел
x
1
,
…
,
x
n
{\displaystyle x_{1},\dots ,x_{n}}
Тоді справедливою є нерівність :
x
1
y
1
+
⋯
+
x
n
y
n
≥
x
σ
(
1
)
y
1
+
⋯
+
x
σ
(
n
)
y
n
≥
x
n
y
1
+
⋯
+
x
1
y
n
.
{\displaystyle x_{1}y_{1}+\cdots +x_{n}y_{n}\geq x_{\sigma (1)}y_{1}+\cdots +x_{\sigma (n)}y_{n}\geq x_{n}y_{1}+\cdots +x_{1}y_{n}.}
Друга нерівність випливає з першої, якщо її застосувати до послідовності
−
x
n
≤
⋯
≤
−
x
1
.
{\displaystyle -x_{n}\leq \cdots \leq -x_{1}.}
Тому достатньо довести лише першу нерівність. Оскільки кількість перестановок є скінченною , принаймні для одної значення суми
x
σ
(
1
)
y
1
+
⋯
+
x
σ
(
n
)
y
n
{\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 . Оскільки
j
<
k
⇒
y
j
≤
y
k
and
j
=
σ
(
k
)
<
σ
(
j
)
⇒
x
j
≤
x
σ
(
j
)
.
(
1
)
{\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)}
Тому,
0
≤
(
x
σ
(
j
)
−
x
j
)
(
y
k
−
y
j
)
.
(
2
)
{\displaystyle 0\leq (x_{\sigma (j)}-x_{j})(y_{k}-y_{j}).\quad (2)}
Розписуючи добуток отримуємо:
x
σ
(
j
)
y
j
+
x
j
y
k
≤
x
j
y
j
+
x
σ
(
j
)
y
k
,
(
3
)
{\displaystyle x_{\sigma (j)}y_{j}+x_{j}y_{k}\leq x_{j}y_{j}+x_{\sigma (j)}y_{k}\,,\quad (3)}
тому перестановка
τ
(
i
)
:=
{
i
i
∈
{
1
,
…
,
j
}
,
σ
(
j
)
i
=
k
,
σ
(
i
)
i
∈
{
j
+
1
,
…
,
n
}
∖
{
k
}
,
{\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 , і також є максимальною. Це суперечить вибору σ.
Якщо
x
1
<
⋯
<
x
n
y
1
<
⋯
<
y
n
,
{\displaystyle x_{1}<\cdots <x_{n}\quad \quad y_{1}<\cdots <y_{n},}
то нерівності (1), (2), і (3) є строгими, тому максимум може бути досягнутим лише в одиничній перестановці.
