你在这里

排序不等式

主标签

定理 (排序不等式 sequence inequality, 又称排序原理) 设 `a_1 \leqslant a_2 \cdots \leqslant a_n,~~b_1 \leqslant b_2 \cdots  \leqslant b_n` 为两组实数, `c_1,~c_2,\cdots,~c_n` 是 `b_1,~b_2,\cdots,~b_n` 的任一排列, 则 $$a_1b_n+a_2b_{n-1}+\cdots +a_nb_1\leqslant a_1c_1+a_2c_2+\cdots +a_nc_n \leqslant a_1b_1+a_2b_2+\cdots +a_nb_n,$$ 当且仅当 `a_1=a_2=\cdots=a_2` 或 `b_1=b_2=\cdots=b_n` 时, 反序和等于顺序和.


排序不等式的证明

设有两组数 `{a_1},{a_2}, \cdot  \cdot  \cdot ,{a_n};{b_1},{b_2}, \cdot  \cdot  \cdot ,{b_n}` ,满足 `{a_1} \le {a_2} \le  \cdot  \cdot  \cdot  \le {a_n},{b_1} \le {b_2} \le  \cdot  \cdot  \cdot  \le {b_n}` 则有

 `{a_1}{b_1} + {a_2}{b_2} +  \cdot  \cdot  \cdot  + {a_n}{b_n}` (顺序和)

 ` \ge `  `{a_1}{b_{{i_1}}} + {a_2}{b_{{i_2}}} +  \cdot  \cdot  \cdot  + {a_n}{b_{{i_n}}}` (乱序和)

 ` \ge {a_1}{b_n} + {a_2}{b_{n - 1}} +  \cdot  \cdot  \cdot  + {a_n}{b_1}`  (逆序和)

其中 `{i_1},{i_2}, \cdot  \cdot  \cdot {i_n}` 是1,2,…,n的一个排列,当且仅当 `{a_1} = {a_2} =  \cdot  \cdot  \cdot  = {a_n}` 或 `{b_1} = {b_2} =  \cdot  \cdot  \cdot  = {b_n}` 时,等号成立.

证明:先证左端,设乱序和为S,要S最大,证明必须 `{a_n}` 配 `{b_n}` , `{a_{n - 1}}` 配 `{b_{n - 1}}` ,…, `{a_1}` 配 `{b_1}` .

设 `{a_n}` 配 `{b_{{i_n}}}({i_n} < n)` , `{b_n}` 配某个 `{a_k}(k < n)` ,下证 `{a_n}{b_{{i_n}}} + {b_n}{a_k} \le {a_k}{b_{{i_n}}} + {a_n}{b_n}` ,

这是因为 `{a_n}{b_n} + {a_k}{b_{{i_n}}} - {a_k}{b_n} - {a_n}{b_{{i_n}}}` = `({a_n} - {a_k})({b_n} - {b_{{i_n}}}) \ge 0` .同理可证 `{a_{n - 1}}` 必配 `{b_{n - 1}}` , `{a_{n - 2}}` 必配 `{b_{n - 2}}` …, `{a_1}` 必配 `{b_1}` ,所以 `{a_1}{b_{{i_1}}} + {a_2}{b_{{i_2}}} +  \cdot  \cdot  \cdot  + {a_n}{b_{{i_n}}}`  ` \le `  `{a_1}{b_1} + {a_2}{b_2} +  \cdot  \cdot  \cdot  + {a_n}{b_n}` .

再证右端.又 `{a_1} \le {a_2} \le  \cdot  \cdot  \cdot  \le {a_n}` , ` - {b_n} \le  - {b_{n - 1}} \le  \cdot  \cdot  \cdot  \le  - {b_1}` ,由以上证明结论(乱序和 ` \le ` 顺序和),可得

 `{a_1}( - {b_n}) + {a_2}( - {b_{n - 1}}) +  \cdot  \cdot  \cdot  + {a_n}( - {b_1}) \ge {a_1}( - {b_{{i_1}}}) + {a_2}( - {b_{{i_2}}}) +  \cdot  \cdot  \cdot  + {a_n}( - {b_{{i_n}}})` .

于是有 `{a_1}{b_n} + {a_2}{b_{n - 1}} +  \cdot  \cdot  \cdot  + {a_n}{b_1}`  ` \le `  `{a_1}{b_{{i_1}}} + {a_2}{b_{{i_2}}} +  \cdot  \cdot  \cdot  + {a_n}{b_{{i_n}}}` .当且仅当 `{a_1} = {a_2} =  \cdot  \cdot  \cdot  = {a_n}` 或

 `{b_1} = {b_2} =  \cdot  \cdot  \cdot  = {b_n}` 时,等号成立.