AM-GM不等式と並び換えの不等式 - 球面倶楽部零八式 mark II

並び換えの不等式、欲張り者の不等式、再配置不等式と色々呼び名があるが，
1987年(昭和62年)東京大学-数学(理科)[5] - [別館]球面倶楽部零八式markIISR
の本質である

$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_jy_j \geqq \displaystyle\sum_{j=1}^{n} x_jz_j$
が成り立つ．

という不等式である．この不等式が欲張り者の不等式と呼ばれる所以は
「日本の硬貨1，5，10，50，100，500円玉について，硬貨Aが5枚，硬貨Bが3枚，硬貨Cが2枚貰えるとする（硬貨A,B,Cはそれぞれ異なる硬貨とする）ならば、硬貨A,B,Cとしてどの硬貨を選ぶか？」という問題は高価なものほど沢山貰えば良いという直観から「Aを500円玉、Bを100円玉、Cを50円玉」とすれば一番お金が貰えることがわかるからである．

この不等式は基本的に $n=2$ の場合の
$x_1\geqq x_2$ ， $y_1\geqq y_2$ ならば
$x_1y_1+x_2y_2\geqq x_1y_2-x_2y_1$ （∵ $(x_1-x_2)(y_1-y_2)\geqq 0$ ）
という不等式を繰り返し有限回用いることによって証明できる．この繰り返し回数が高々 ${}_n\mbox{C}_2$ となるのはバブルソートを行なっていることからもわかる．

この不等式を利用して2008年に高校の先生がAM-GM不等式の新しい証明を発見したとして話題となった．
A SIMPLE PROOF OF THE GEOMETRIC-ARITHMETIC MEAN INEQUALITY (pdf)

この証明の概略を述べる．

示すべき不等式は $a_1\geqq a_2\geqq \cdots \geqq a_n\gt 0$ のとき
$a_1^n+a_2^n+\cdots +a_n^n\geqq n a_1a_2\cdots a_n$
であり，帰納法で示している．

$n=2$ のときは $(a_1-a_2)\geqq 0$ より成立する．

$n=k$ のときに $a_1^k+a_2^k+\cdots +a_k^k\geqq k a_1a_2\cdots a_k$ の成立を仮定する．

$n=k+1$ のとき，
$a_1^{k+1}+a_2^{k+1}+\cdots +a_k^{k+1}+a_{k+1}^{k+1}$
$\geqq a_1^{k+1}+a_2^{k+1}+\cdots +(a_{k+1})(a_k^k) +(a_k)(a_{k+1}^{k})$
（∵ $a_k\geqq a_{k+1}$ かつ $a_k^k\geqq a_{k+1}^k$ ）
$=a_1^{k+1}+a_2^{k+1}+\cdots +a_{k-1}^{k+1}+a_{k+1} a_k^k +a_k a_{k+1}^{k}$
$\geqq a_1^{k+1}+a_2^{k+1}+\cdots +(a_{k+1})(a_{k-1}^{k})+a_{k+1}a_k^k +(a_{k-1})(a_k a_{k+1}^{k-1})$
（∵ $a_{k-1}\geqq a_{k+1}$ かつ $a_{k-1}^k\geqq a_k a_{k+1}^{k-1}$ ）
$=a_1^{k+1}+a_2^{k+1}+\cdots +a_{k-2}^{k+1}+a_{k+1}(a_{k-1}^{k}+a_k^k) +a_{k-1}a_k a_{k+1}^{k-1}$
$\geqq a_1^{k+1}+a_2^{k+1}+\cdots +(a_{k+1})(a_{k-2}^{k})+a_{k+1}(a_{k-1}^{k}+a_k^k) +(a_{k-2})(a_{k-1}a_ka_{k+1}^{k-2})$
（∵ $a_{k-2}\geqq a_{k+1}$ かつ $a_{k-2}^k\geqq a_{k-1}a_ka_{k+1}^{k-2}$ ）
$\cdots\cdots$
$\geqq a_{k+1}(a_1^{k}+a_2^{k}+\cdots +a_k^k) +a_1a_2\cdots a_{k-2}a_{k-1}a_ka_{k+1}$
であり，仮定から
$a_{k+1}(a_1^{k}+a_2^{k}+\cdots +a_k^k) +a_1a_2\cdots a_{k-2}a_{k-1}a_ka_{k+1}$
$\geqq a_{k+1}(ka_1a_2\cdots a_k) +a_1a_2\cdots a_{k-2}a_{k-1}a_ka_{k+1}$ $=(k+1)a_1a_2\cdots a_k a_{k+1}$
となるので， $n=k+1$ のときも成立する．

というものである．この並び換えの不等式を利用した AM-GM 不等式の証明は，実は以前から知られており，

雑誌大学への数学1970年9月号p27の「ある不等式の証明」

という高校2年生の読者からの記事で証明されている．

この記事では，入れ替えを利用して AM-GM 不等式を示すことも行っている．この記事は1ページの短いもので，記事自体が証明の概略を述べるに留まっているが，より一般的な並び換えの不等式を述べて，その適用例として AM-GM 不等式を行っている．雑誌の記事とは異なる記法で証明を述べる（当該記事の証明はもっとエレガントな記法を用いて表現している）．

$x_{i1}\geqq x_{i2}\geqq\,\cdots\,\geqq x_{in}\gt 0$ （ $i=1,2,\cdots,m$ ）を満足する数列
$x_{i1}$ ， $x_{i2}$ ，…， $x_{in}$ （ $i=1,2,\cdots,m$ ）が与えられている．
$x_{i1}$ ， $x_{i2}$ ，…， $x_{in}$ 　を並べかえて得られるどのような数列
$z_{i1}$ ， $z_{i2}$ ，…， $z_{in}$ （ $i=1,2,\cdots,m$ ）に対しても

$\displaystyle\sum_{j=1}^n \prod_{k=1}^{m} x_{kj} \geqq \sum_{j=1}^n \prod_{k=1}^{m} z_{kj}$

が成立する．

を $n$ （ $\geqq 2$ ）についての帰納法で示す．

$n=2$ のとき
$\displaystyle \prod_{k=1}^{m} x_{k1} + \prod_{k=1}^{m} x_{k1} \geqq \prod_{k=1}^{m} z_{k1}+\prod_{k=1}^{m} z_{k2}$
を示せば良い．ここで $z_{k1}=x_{k1}$ となっている添字 $k$ の集合を ${\cal K_1}$ ，そうでない添字 $k$ の集合を ${\cal K_2}$ とする．ここでそれぞれの集合のうち片方が空集合だとすると，全く入れ換えていないか全部入れ換えたということなので明らかに等号が成立するので，両方とも空でないとする．このとき，
$\displaystyle X_{11}=\prod_{k\in{\cal K_1}} x_{k1} = \prod_{k\in{\cal K_1}} z_{k1}=Z_{11}$ ，
$\displaystyle X_{21}=\prod_{k\in{\cal K_2}} x_{k1} = \prod_{k\in{\cal K_2}} z_{k2}=Z_{22}$ ，
$\displaystyle X_{12}=\prod_{k\in{\cal K_1}} x_{k2} = \prod_{k\in{\cal K_1}} z_{k2}=Z_{12}$ ，
$\displaystyle X_{22}=\prod_{k\in{\cal K_2}} x_{k2} = \prod_{k\in{\cal K_2}} z_{k1}=Z_{21}$
とすると，
$X_{11}，X_{12}$ の入れ換えが $Z_{11}，Z_{12}$ （入れ換えてない），
$X_{21}，X_{22}$ の入れ換えが $Z_{21}，Z_{22}$ （入れ換えている）
であり，
$X_{11}\geqq X_{12}$ ， $X_{21}\geqq X_{22}$ （この不等式が必ず成立するために $x_{kj}\gt 0$ という条件がある）
であるから
$X_{11}X_{21}+X_{12}X_{22} \geqq Z_{11}Z_{21}+Z_{12}Z_{22}$
つまり，
$\displaystyle \prod_{k=1}^{m} x_{k1} + \prod_{k=1}^{m} x_{k1} \geqq \prod_{k=1}^{m} z_{k1}+\prod_{k=1}^{m} z_{k2}$
が成立する．

$n=k$ の成立を仮定する．

$n=k+1$ のとき，
$z_{i1}$ ， $z_{i2}$ ，…， $z_{i,k+1}$ （ $i=1,2,\cdots,m$ ）に対して
後ろの添字の $1〜k$ までに $n=k$ の仮定を適用し，次に後ろの添字の $2〜k+1$ までに $n=k$ の仮定を適用し，最後に後ろの添字の $1〜k$ までに $n=k$ の仮定を適用すると
$z_{i1}$ ， $z_{i2}$ ，…， $z_{i,k+1}$ （ $i=1,2,\cdots,m$ ）
は整序されて
$x_{i1}$ ， $x_{i2}$ ，…， $x_{i,k+1}$ （ $i=1,2,\cdots,m$ ）
の順番となることから， $n=k+1$ のときも成立する．

以上から任意の $n\geqq 2$ について成立する．

（この不等式が必ず成立するために $x_{kj}\gt 0$ という条件がある，という部分について，もし正という条件がなければ， $2\geqq -1$ ， $0\geqq -1$ だが $0\leqq 1$ という反例が見つかる）

この並び換えの不等式の一般化において $m=n$ とし，
$a_{1}\geqq a_{2}\geqq\,\cdots\,\geqq a_{n}\gt 0$ （ $i=1,2,\cdots,n$ ）を満足する数列に対し，
$x_{i1}=a_1$ ， $x_{i2}=a_2$ ，…， $x_{in}=a_n$ （for all $i=1,2,\cdots,n$ ）
とし，その並び換えとして
$z_{i1}=a_{i}$ ， $z_{i2}=a_{i+1}$ ，…， $z_{in}=a_{i+n-1}$ （ $i=1,2,\cdots,n$ ）
を考える（添字が $n$ を超えたら $n$ を引く）と
$\displaystyle\sum_{j=1}^n \prod_{k=1}^{n} x_{kj}$ $=\displaystyle\sum_{j=1}^n a_j^n$ ，
$\displaystyle\sum_{j=1}^n \prod_{k=1}^{n} z_{kj}$ $=\displaystyle\sum_{j=1}^n \prod_{k=1}^{n} a_k=n\prod_{k=1}^{n} a_k$
となるので，
$\displaystyle\sum_{j=1}^n a_j^n\geqq n\prod_{k=1}^{n} a_k$
が成立し，AM-GM 不等式の証明が完了する．