定义

对于两个序列 $a_1 \geq a_2 \geq \dots \geq a_n$ 和 $b_1 \geq b_2 \geq \dots \geq b_n$,则有不等式:

$\sum\limits_{i=1}^{n} a_ib_i\geq \sum\limits_{i=1}^{n} a_ib_{\pi(i)} \geq \sum\limits_{i=1}^{n} a_1b_{n-i+1}$

其中 $\pi(i)$ 是任意一个 $n$ 阶排列。

证明

假如排列 $\pi(i)$ 使 $\sum\limits_{i=1}^{n} a_{i}b_{\pi(i)}$ 最大,那么 $\pi(i)$ 是一个确定的排列即 $\forall i, \pi(i) = i$。假设该结论不成立,那么 $\pi(i)$ 为一个乱序 $n$ 阶排列且 $\exists i, \pi(i) \neq i$,设 $i$ 是排列 $\pi$ 的第一个出现 $\pi(i) \neq i$ 的位置。

$i$ 是第一个这样的位置,那么 $\pi(i) = j > i$,并且一定存在一个 $k >i$ 有 $\pi(k) = i$。

因为 $i<j$ 那么 $b_i \leq b_j$,同时有:因为 $i < k$,那么 $a_i \leq a_k$。因此:

$$ (a_k - a_j)(b_j - b_i) \geq 0 \Longrightarrow a_ib_i + a_jb_j \geq a_ib_j + a_jb_i $$

所以通过使 $\pi(i) = j, \pi(k) = i$ 变成 $\pi(i) = i, \pi(j) = j$, $\sum\limits_{i=1}^{n} a_ib_{\pi(i)}$ 单调不减。

证毕。

最后修改:2021 年 11 月 01 日
如果觉得我的文章对你有用,请随意赞赏