東北大学 2010年度 後期日程 第2次学力試験理系（後期）数学 第1問

$z_1,\dots ,z_n$ が $y_1,\dots ,y_n$ の並べ替えであるとする。もし $i<j$ で $z_i<z_j$ となる組があれば，$z_i$ と $z_j$ は大きい順に並んでいない。

この2つだけを入れ替えたときの2乗和の変化を調べる。入れ替える前の該当部分は $(x_i-z_i{)}^2+(x_j-z_j{)}^2$ であり，入れ替えた後は $(x_i-z_j{)}^2+(x_j-z_i{)}^2$ である。差を取ると $\{(x_i-z_i{)}^2+(x_j-z_j{)}^2\}-\{(x_i-z_j{)}^2+(x_j-z_i{)}^2\}$ $=2(x_i-x_j)(z_j-z_i)\mathrm{.}$ ここで $i<j$ より $x_i>x_j$ であり，また仮定より $z_j>z_i$ である。したがって $2(x_i-x_j)(z_j-z_i)>0$ である。つまり，このような逆転を入れ替えると，2乗和は厳密に小さくなる。

この操作を繰り返すと，$z_1,z_2,\dots ,z_n$ は大きい順に並ぶ。$y_1>y_2>\cdots >y_n$ であり，$z_i$ は $y_i$ の並べ替えなので，最終的には $$z_i=y_i(i=1,2,\dots ,n)$$ となる。この過程で和は増えず，逆転があれば厳密に小さくなる。したがって $$\sum _{i=1}^n(x_i-y_i{)}^2\leqq \sum _{i=1}^n(x_i-z_i{)}^2$$ が成り立つ。

等号について考える。もし $z_i$ が $y_i$ と同じ順でなければ，ある $i<j$ について $z_i<z_j$ となる逆転が存在し，上の交換で2乗和が厳密に小さくなる。したがって等号は成り立たない。

よって等号が成り立つのは，はじめから $$z_i=y_i(i=1,2,\dots ,n)$$ であるとき，かつそのときに限られる。

両辺の平方和を展開する。$z_i$ は $y_i$ の並べ替えなので定数部分は一致し、問題は $\sum x_i{y}_i$ が $\sum x_i{z}_i$ 以上であることへ帰着する。最大の $y_1$ を先頭へ移す交換を繰り返し、帰納的に順序を確定する。

まず$$\sum _{i=1}^n(x_i-z_i{)}^2-\sum _{i=1}^n(x_i-y_i{)}^2$$を展開する。$z_1,\dots ,z_n$ は $y_1,\dots ,y_n$ の並べ替えだから$$\sum _{i=1}^n{z}_i^2=\sum _{i=1}^n{y}_i^2$$であり、$$\sum _{i=1}^n(x_i-z_i{)}^2-\sum _{i=1}^n(x_i-y_i{)}^2=2(\sum _{i=1}^n{x}_i{y}_i-\sum _{i=1}^n{x}_i{z}_i)\mathrm{.}$$そこで右辺の括弧が非負であることを示す。並び $z_1,\dots ,z_n$ の中で最大の数 $y_1$ が第 $k$ 項にあるとする。$k>1$ なら $z_1<y_1$ である。$z_1$ と $z_k=y_1$ を交換したとき、和 $\sum x_i{z}_i$ の増加量は$$x_1{y}_1+x_k{z}_1-(x_1{z}_1+x_k{y}_1)=(x_1-x_k)(y_1-z_1)>0$$である。よって最大値を与える並びでは必ず $z_1=y_1$ でなければならない。

残る $n-1$ 項にも同じ議論を順に適用すると、$\sum x_i{z}_i$ が最大となるのは$$z_i=y_i(i=1,\dots ,n)$$のときだけである。したがって$$\sum _{i=1}^n{x}_i{y}_i\geqq \sum _{i=1}^n{x}_i{z}_i\mathrm{.}$$これを最初に展開した差の式へ戻せば、求める不等式を得る。

また $x_i$、$y_i$ はいずれも狭義減少列なので、順序が1か所でも異なれば上の交換で和は厳密に増える。よって等号成立は$$z_i=y_i(i=1,\dots ,n)$$のとき、かつそのときに限る。