2014/03/30

並べ替え不等式の証明と例題

分野: 不等式  レベル: 数学オリンピック

並べ替え不等式(rearrangement inequality):
$x_1\geq x_2\geq\cdots\geq x_n\\y_1\geq y_2\geq\cdots \geq y_n$,
$1, 2, \cdots, n$ の並べ替え $\sigma(1), \sigma(2), \cdots, \sigma(n)$ に対して,
$\displaystyle\sum_{i=1}^nx_iy_i\geq\sum_{i=1}^nx_iy_{\sigma(i)}\geq\sum_{i=1}^nx_iy_{n-i+1}$

並べ替え不等式のイメージ

一般の場合の表現では分かりにくいので $n=3$ の場合を考えてみます。

100円玉,50円玉,10円玉のうちどれかを3枚,どれかを2枚,どれかを1枚もらえるとしたら,100円玉をいっぱいもらうと思います。
$100\times 3+50\times 2+10\times 1\geq$ もらえる金額
逆に,お金を上げる場合を考えると,10円玉をいっぱいあげると思います。
払う金額 $\geq100\times 1+50\times 2+10\times 3$

これが $x_1=100, x_2=50, x_3=10,y_1=3, y_2=2, y_3=1$ の場合の並べ替え不等式になります。式で書くといまいちピンときづらいですが,直感的に「大きい数字をたくさん集めたほうが大きくなる」という当たり前な不等式です。

証明はそんなにエレガントじゃないですが,応用例はエレガントなので先に応用例から紹介します。

並べ替え不等式の応用例

例題1

$a^2+b^2+c^2\geq ab+bc+ca$ を示せ。

方針:対称式の不等式証明は自由に大小関係を定めることができるので並べ替え不等式が使えます。

解答

$a\geq b\geq c$ の場合にのみ証明すればよい。
並べ替え不等式において,$x_1=y_1=a, x_2=y_2=b, x_3=y_3=c$ とすれば題意の不等式を得る:$a^2+b^2+c^2\geq ab+bc+ca$

「大きい数字をたくさん集めたほうが大きくなる」というのは覚えておきましょう。
ちなみにこの有名不等式は他にもいろいろな方法で証明できます。(→有名不等式a^2+b^2+c^2≧ab+bc+ca証明

例題2

$a, b, c > 0$ のとき以下の不等式を証明せよ。
$\dfrac{a}{b+c}+\dfrac{b}{c+a}+\dfrac{c}{a+b}\geq \dfrac{3}{2}$

方針:先ほどと同様に対称式なので大小関係を設定してから並べ替え不等式が使えそうです。右辺の $\dfrac{3}{2}$ を出すために一工夫必要になります。

解答

$a\geq b\geq c$ の場合にのみ証明すればよい。
$a+b\geq c+a\geq b+c$ より,$\dfrac{1}{b+c}\geq \dfrac{1}{c+a}\geq \dfrac{1}{a+b}$
よって並べ替えの不等式より,
$\dfrac{a}{b+c}+\dfrac{b}{c+a}+\dfrac{c}{a+b}\geq\dfrac{b}{b+c}+\dfrac{c}{c+a}+\dfrac{a}{a+b}\\
\dfrac{a}{b+c}+\dfrac{b}{c+a}+\dfrac{c}{a+b}\geq\dfrac{c}{b+c}+\dfrac{a}{c+a}+\dfrac{b}{a+b}$
この2つの不等式を辺々加えて2で割ると求める不等式が得られる。

ちなみにこの不等式はNesbittの不等式と呼ばれる有名不等式で他にも様々な方法で証明できます。Nesbittの不等式の6通りの証明

並べ替え不等式の証明

方針:$\sigma$ を動かして全ての並べ替えを試した時に,$\displaystyle\sum_{i=1}^nx_iy_{\sigma(i)}$ が最大となるのが $\sigma(i)=i$(恒等変換)であることを示せばよい。

置換の記号を使っていて一見難しいですが,要するに「 $x_1$ の相方が $y_1$ じゃないときは交換によって値を大きくできる」ことを言うだけです。

証明

$\sigma(1)=i\neq 1$ のとき $\sigma(j)=1$ となる $1$ でない $j$ が存在する。
$(x_1-x_j)(y_1-y_i)\geq 0$ より,
$x_1y_1+x_jy_i\geq x_1y_i+x_jy_1$,つまり
$x_1y_{\sigma(j)}+x_jy_{\sigma(1)}\geq x_1y_{\sigma(1)}+x_jy_{\sigma(j)}$
よって,$y_{\sigma(1)}$ と $y_{\sigma(j)}$ を交換しても(すなわち $x_1$ の相方と $x_j$ の相方を交換しても)値は小さくならない。よって,最大の値となる並べ替え(の1つ)を $\sigma’$とおくと,$\sigma'(1)=1$ を満たす。つまり,$x_1$ の相方は $y_{\sigma(j)}=y_1$ の方がよいということ!

同様にして最大の値をとる並べ替え(の1つ)$\sigma’$は,任意の $i$ に対して $\sigma'(i)=i$ を満たすことが分かる。
つまり,$\displaystyle\sum_{i=1}^nx_iy_i\geq\sum_{i=1}^nx_iy_{\sigma(i)}$


次に,$y_i$ を逆方向から並べ替えて,
$-y_n\geq -y_{n-1}\geq\cdots\geq -y_1$ としたものに上記で示した不等式を適用する:
$\displaystyle\sum_{i=1}^nx_i(-y_{n-i+1})\geq\sum_{i=1}^nx_i(-y_{\sigma(i)})$
これより右側の不等式を得る:
$\displaystyle\sum_{i=1}^nx_iy_{\sigma(i)}\geq\sum_{i=1}^nx_iy_{n-i+1}$

ごちゃごちゃしていますが,本質的に重要なのは「恒等変換以外は交換して値を改善できる」という事実だけです。

「大きい数字を集めたほうが大きくなる」というのはMuirheadの不等式に通じるものを感じますねえ

対称式の不等式は大小関係設定して並べ替え不等式が使えることが多い

Tag: 数学オリンピック突破のための有名不等式まとめ

分野: 不等式  レベル: 数学オリンピック