1987年(昭和62年)東京大学-数学(理科)[5] - [別館]球面倶楽部零八式markIISR

2023.08.29記

[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$ ，…， $x_n$ および $y_1$ ， $y_2$ ，…， $y_n$ が与えられている． $y_1$ ， $y_2$ ，…， $y_n$ を並べかえて得られるどのような数列 $z_1$ ， $z_2$ ，…， $z_n$ に対しても
$\displaystyle\sum_{j=1}^{n} (x_j-y_j)^2 \leqq \displaystyle\sum_{j=1}^{n} (x_j-z_j)^2$
が成り立つことを証明せよ．

本問のテーマ

並び換えの不等式（欲張り者の不等式）
バブルソート(2023.08.30)

2021.01.20記
本問は並び換えの不等式（欲張り者の不等式）に帰着され，それを証明せよという問題である．チェビシェフの和の不等式も並び換えの不等式（欲張り者の不等式）を用いて証明される．

[解答]
$\displaystyle\sum_{j=1}^n y_j^2=\sum_{j=1}^n z_j^2$ だから，
$\displaystyle\sum_{j=1}^n x_jy_j\geqq \sum_{j=1}^n x_jz_j$ を示せば良い．

$n=2$ のとき， $y_1,y_2$ の並べかえは，
$y_1=z_1,y_2=z_2$ ， $y_1=z_2,y_2=z_1$ の2通りで，
前者は $(x_1y_1+x_2y_2)-(x_1z_1+x_2z_2)=0$ ，
後者は $(x_1y_1+x_2y_2)-(x_1z_1+x_2z_2)$ $=(x_1-x_2)(y_1-y_2)\geqq 0$
となるので題意は成立する．

$n=2,\ldots, k$ で題意が成立すると仮定する．
$n=k+1$ のとき， $z_2,\ldots,z_{k+1}$ を大きい順に並べ換えたものを $w_2,\ldots,w_{k+1}$ とし， $z_1,w_2,\ldots,w_{k}$ を大きい順に並べ換えたものを $v_1,\ldots,v_{k}$ とすると， $v_1=y_1$ である．
そして， $v_2,\ldots,v_{k}, w_{k+1}$ を大きい順に並べ換えたものは $y_2,\ldots,y_{k+1}$ である．

よって帰納法の仮定により，
$\displaystyle\sum_{j=1}^{k+1} x_jz_j\leqq x_1z_1 +\sum_{j=2}^{k+1} x_jw_j$ $=\displaystyle x_1y_1 +\sum_{j=2}^{k} x_jv_j+x_{k+1}w_{k+1}$ $=\displaystyle x_1y_1 +\sum_{j=2}^{k+1} x_jy_j$
であるから， $n=k+1$ のときも題意は成立する．

よって数学的帰納法により $2$ 以上の任意の自然数にたいして題意は成立する．

~~この出題あたりから，東大入試に Putnam Competition の問題が出ると言われはじめた。~~
（2023.08.31に補足したが，本問は Putnam ではなくて IMO だった）

2023.08.30記
当時の大数の解答もそうであるが，多くの解答は帰納法を使わずに
「 $n=2$ のときの並び換え（入れ換え）を一般の $n$ の場合に高々有限回適用すれば良い」
という方針で解いている．これを組織的に行うには 2個の入れ換えを繰り返すことによって全体を並び換える手法であるバブルソートを行えば良いことになる．よって大数でも指摘しているように高々 ${}_n\mbox{C}_2$ 回の入れ替えで $z_i$ は $y_i$ になることがわかる．

[解答]はバブルソートがうまく行く理由を帰納法を用いて示していると解釈することもできる．このバブルソート的に入れ替えを行うことによってこの並び換えの不等式を示す方法は雑誌大学への数学1970年9月号p27の「ある不等式の証明」という高校2年生の読者からの記事にある．

この記事では，入れ替えを利用して AM-GM 不等式を示すことも行っている．

2008年に高校の先生が新しい証明を発見したとして話題となった
A SIMPLE PROOF OF THE GEOMETRIC-ARITHMETIC MEAN INEQUALITY (pdf)
も並び換えの不等式を利用した証明となっているが，この証明は実質先程紹介した大数の記事と同じ．

（ここに書いていた文書は内容を強化して
AM-GM不等式と並び換えの不等式 - 球面倶楽部零八式 mark II
に記述した(2023.8.31)）

2023.08.31記
以前，「この出題あたりから，東大入試に Putnam Competition の問題が出ると言われはじめた。」と書いたが，これは嘘ではないのだが、本問は IMO1975(ブルガリア大会)の1番そのものだった．

Let $x_i,y_i(i=1,2,\ldots,n)$ be real numbers such that
$x_1\geqq x_2\geqq\,\cdots\,\geqq x_n$ and $y_1\geqq y_2\geqq\,\cdots \,\geqq y_n$ .

Prove that, if $z_1$ ， $z_2$ ，…， $z_n$ is any permutation of $y_1$ ， $y_2$ ，…， $y_n$ , then
$\displaystyle\sum_{j=1}^{n} (x_j-y_j)^2 \leqq \displaystyle\sum_{j=1}^{n} (x_j-z_j)^2$ .

そのまんまだった．このころはまだ日本は IMO に参加していなかった（参加は1990年北京大会から）．

あと，この入れ換えに関して「 $z_1〜z_{n}$ の中の最小値と $z_{n}$ と入れ換え」，次に「 $z_1〜z_{n-1}$ の中の最小値と $z_{n-1}$ と入れ換え」，…
と繰り返すと高々 $n-1$ 回の入れ換えで $z$ は $x$ に整序される，と表現することもできる．