東京大学 1987年度 前期日程 第2次学力試験理系数学 第5問

任意の並べ替え $z_1,z_2,\dots ,z_n$ を考える。もしある $i<j$ について $z_i<z_j$ となっていれば、この2項の順序は $x_i\geqq x_j$ とは逆になっている。この2項だけを交換したとき、二乗和の変化を調べる。

交換前の該当部分は $(x_i-z_i{)}^2+(x_j-z_j{)}^2$ であり、交換後は $(x_i-z_j{)}^2+(x_j-z_i{)}^2$ である。差を計算すると$$\begin{array}{rl}{\displaystyle }& {\displaystyle \{(x_i-z_i{)}^2+(x_j-z_j{)}^2\}-\{(x_i-z_j{)}^2+(x_j-z_i{)}^2\}}\\ {\displaystyle }& {\displaystyle =2(x_i-x_j)(z_j-z_i)\mathrm{.}}\end{array}$$ここで $x_i\geqq x_j$、$z_j>z_i$ だから $2(x_i-x_j)(z_j-z_i)\geqq 0$ である。したがって、この交換を行うと二乗和は増えない。

この操作を、$z$ の中で順序が逆になっている2項がなくなるまで繰り返す。各交換で二乗和は増えず、最終的には $$z_1\geqq z_2\geqq \cdots \geqq z_n$$ となる。ところが $z_1,\dots ,z_n$ は $y_1,\dots ,y_n$ の並べ替えであり、もともと $$y_1\geqq y_2\geqq \cdots \geqq y_n$$ だから、最終的な並びは $y_1,y_2,\dots ,y_n$ である。

よって任意の並べ替え $z$ に対して $$\sum _{j=1}^n(x_j-y_j{)}^2\leqq \sum _{j=1}^n(x_j-z_j{)}^2$$ が成り立つ。

二乗和を最小にする並べ方を一つ取る。最大の $x_1$ に最大の $y_1$ が対応していなければ、その二つの対応先を交換して和が増えないことを示す。$x_1,y_1$ を固定した後、残る $n-1$ 項に同じ議論を適用する。

$n$ に関する帰納法で示す。$n=2$ のときは$$\begin{array}{rl}{\displaystyle }& {\displaystyle (x_1-y_2{)}^2+(x_2-y_1{)}^2}\\ {\displaystyle }& {\displaystyle -\{(x_1-y_1{)}^2+(x_2-y_2{)}^2\}}\\ {\displaystyle }& {\displaystyle =2(x_1-x_2)(y_1-y_2)\geqq 0}\end{array}$$だから成り立つ。

$n-1$ 項まで成り立つと仮定する。任意の並べ替え $z_1,\dots ,z_n$ の中で、$y_1$ が $k$ 番目にあるとする。$z_1$ と $z_k=y_1$ を交換したとき、交換前から交換後を引くと$$2(x_1-x_k)(y_1-z_1)\geqq 0$$である。したがって、$y_1$ を $x_1$ に対応させても二乗和は増えない。

残る $x_2,\dots ,x_n$ と $y_2,\dots ,y_n$ はいずれも降順である。帰納法の仮定により、この残りも同じ順に対応させたとき二乗和が最小になる。よって全体でも$$\sum _{j=1}^n(x_j-y_j{)}^2\leqq \sum _{j=1}^n(x_j-z_j{)}^2$$が成り立つ。