排序不等式
你可以在这里下载本文的 PDF.
若两组实数 a_1, a_2, \cdots, a_n; b_1, b_2, \cdots, b_n 满足 a_1 \leq a_2 \leq \ldots \leq a_n; b_1 \leq b_2 \leq \ldots \leq b_n, 那么
\sum_{j=1}^n x_j y_{n-j+1} \leq \sum_{j=1}^n x_j y_{i_j} \leq \sum_{j=1}^n x_j y_j,
其中 i_1, i_2, \cdots, i_n 是 1, 2, dots, n 的一个排列.
证明
记 S = a_1 b_{i_1} + a_2 b_{i_2} + \ldots + a_k b_{i_k} + \ldots + a_n b_{i_n}. 若 b_{i_n} \neq b_n, 则必有 b_{i_k} = b_n, 因此设
S_1 = a_1 b_{i_1} + a_2 b_{i_2} + \ldots + a_k b_{i_n} + \ldots + a_n b_{i_k},
于是有
\begin{align*}
S-S_1 &= a_k b_{i_k} + a_n b_{i_n} - a_k b_{i_n} - a_n b_{i_k} \\
&= (a_k - a_n)(b_{i_k} - b_{i_n}) \\
&\leq 0,
\end{align*}
即
S \leq S_1.
接下来, 若 b_{i_{n-1}} \neq b_{n-1}, 则继续用同样的方法调整. 在足够多的 m 次调整后, 一定有
S_m = a_1 b_1 + a_2 b_2 + \ldots + a_n b_n,
S \leq S_1 \leq \ldots \leq S_m
这样就证明了
\sum_{j=1}^n x_j y_{i_j} \leq \sum_{j=1}^n x_j y_j.
对于 \displaystyle \sum_{j=1}^n x_j y_{n-j+1} \leq \sum_{j=1}^n x_j y_{n_j}, 可采取类似的方法说明, 这里不再赘述.