Loading... ## 定义 对于两个序列 $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 \geq b_j$,同时有:因为 $i < k$,那么 $a_i \geq 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)}$ 单调不减。 证毕。 最后修改:2024 年 01 月 11 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 2 如果觉得我的文章对你有用,请随意赞赏
1 条评论
受益匪浅