空論上の砂、楼閣上の机。

The Castle of Indolence

並べ替え不等式・Chebyshev の不等式 (1987年 東大理系 第5問, 1986年 京大文理共通 第1問)

今回の記事はどうしても横に長くなるので横スクロールしていただく数式がそれなりに多くあります. PC やタブレットの場合は問題なく表示されますが, スマートフォンなどの場合で不自然だと思ったら右のスクロールしていただくようお願い申し上げます.
定理1. (並べ替え不等式) 単調減少列 $\{x _ n\},$ $\{y _ n\}$ と, 置換 $\sigma\colon\{1,\dots,n\}\to\{1,\dots,n\}$ に対し $$\displaystyle\sum_{i=1}^nx_iy_i\geqq\sum_{i=1}^nx_iy_{\sigma(i)}\geqq\sum_{i=1}^nx_iy_{n-i+1}$$

これは本質的に次の問題と同じです.

問題2. (1987年 東大理系 第5問) $n$ を $2$ 以上の自然数とする. $x_1\geqq x_2\geqq\cdots\geqq x_n$ および $y_1\geqq y_2\geqq\cdots\geqq y_n$ を満足する数列 $x_1, x_2,\dots,x_n$ および $y_1,y_2,\dots,y_n$ が与えられている. $y_1,y_2,\dots,y_n$ を並びかえて得られるどのような数列 $z_1,z_2,\dots,z_n$ に対しても $$\sum_{j=1}^n(x_j-y_j)^2\leqq\sum_{j=1}^n(x_j-z_j)^2$$ が成り立つことを証明せよ.
証明. 示すべき不等式は $$\sum _ {j=1} ^ n x _ j(y _ j-z _ j)\geqq 0$$ に等しく, Abel の総和公式
$$\begin{aligned} \sum_{i=1}^n a_ib_i=&\,(a_1-a_2)b_1+(a_2-a_3)(b_1+b_2)+\cdots\\ &+(a_{n-1}-a_n)(b_1+\cdots+b_{n-1})+a_n(b_1+\cdots+b_n) \end{aligned}$$
を用いて次のように示される.
$$\begin{aligned} \sum_{j=1}^n x_j(y_j-z_j) =&\,\underbrace{(x_1-x_2)}_{\geqq 0}\underbrace{(y_1-z_1)}_{\geqq 0}+\underbrace{(x_2-x_3)}_{\geqq 0}\underbrace{(y_1+y_2-z_1-z_2)}_{\geqq 0}\\ &+\cdots\\ &+\underbrace{(x_{n-1}-x_{n})}_{\geqq 0}\underbrace{\left(\sum_{j=1}^{n-1}y_j-\sum_{j=1}^{n-1}z_j\right)}_{\geqq 0}\\ &+\underbrace{x_n}_{\geqq0}\underbrace{\left(\sum_{j=1}^n y_j-\sum_{j=1}^n z_j\right)}_{\geqq 0} \end{aligned}$$

並び替え不等式から容易に得られる系として次があります.

系3. (Chebyshev の不等式) 単調減少列 $\{x_n\}, \{y_n\}$ に対し,
$$\dfrac{1}{n}\displaystyle\sum_{i=1}^nx_iy_i\geqq\left(\dfrac{1}{n}\sum_{i=1}^nx_i\right)\left(\dfrac{1}{n}\sum_{i=1}^ny_i\right)\geqq\dfrac{1}{n}\sum_{i=1}^nx_iy_{n+1-i}$$

これを意識するだけで至極簡単に解けるのが次の問題です.

問題4. (1986年 京大文理共通 第1問) すべては $0$ でない $n$ 個の実数 $a _ 1, a _ 2, \dots, a_n$ があり, $a_1\leqq a_2\leqq\cdots\leqq a_n$ かつ $a_1+a_2+\cdots+a_n=0$ を満たすとき, $a_1+2a_2+\cdots+na_n>0$ が成り立つことを証明せよ.
証明. Chebyshev の不等式より
$$\dfrac{a_1+2a_n+\cdots+na_n}{n}\geqq\dfrac{a_1+a_2+\cdots+a_n}{n}\dfrac{1+2+\cdots+n}{n}=0.$$