1. 高校数学の美しい物語
  2. 並べ替え不等式の証明と例題

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

更新日時 2021/03/07
並べ替え不等式(rearrangement inequality)
  • x1x2xnx_1\geq x_2\geq\cdots\geq x_n
  • y1y2yny_1\geq y_2\geq\cdots \geq y_n
  • {1,2,,n}\{1, 2, \cdots, n\} の並べ替え {σ(1),σ(2),,σ(n)}\{\sigma(1), \sigma(2), \cdots, \sigma(n)\}

に対して,

i=1nxiyii=1nxiyσ(i)i=1nxiyni+1\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=3n=3 の具体例を考えてみます。

100円玉,50円玉,10円玉のうちどれかを3枚,どれかを2枚,どれかを1枚もらえるとしたら,100円玉をいっぱいもらうと思います。つまり,

100×3+50×2+10×1100\times 3+50\times 2+10\times 1\geq もらえる金額

になりそうです。逆に,お金を上げる場合は10円玉をいっぱいあげると思います。つまり,

払う金額 100×1+50×2+10×3\geq100\times 1+50\times 2+10\times 3

になりそうです。

これが n=3,x1=100,x2=50,x3=10,y1=3,y2=2,y3=1n=3,x_1=100, x_2=50, x_3=10,y_1=3, y_2=2, y_3=1 の場合の並べ替え不等式

i=13xiyii=13xiyσ(i)i=13xiy4i\displaystyle\sum_{i=1}^3x_iy_i\geq\sum_{i=1}^3x_iy_{\sigma(i)}\geq\sum_{i=1}^3x_iy_{4-i}

になります。式で書くと少しわかりにくいですが,直感的に 「大きい数字をたくさん集めたほうが大きくなる」という当たり前な不等式です。

証明は後ほど紹介します。先に美しい応用例から紹介します。

並べ替え不等式の応用例

例題1

a2+b2+c2ab+bc+caa^2+b^2+c^2\geq ab+bc+ca を示せ。

方針

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

解答

abca\geq b\geq c の場合にのみ証明すればよい。

並べ替え不等式において,

x1=y1=a,x2=y2=b,x3=y3=cx_1=y_1=a, x_2=y_2=b, x_3=y_3=c

とすれば目標の不等式を得る:

a2+b2+c2ab+bc+caa^2+b^2+c^2\geq ab+bc+ca

「大きい数字をたくさん集めたほうが大きくなる」というのは覚えておきましょう。

ちなみにこの有名不等式は他にもいろいろな方法で証明できます(→有名不等式a^2+b^2+c^2≧ab+bc+ca証明)。

例題2

a,b,c>0a, b, c > 0 のとき以下の不等式を証明せよ。

ab+c+bc+a+ca+b32\dfrac{a}{b+c}+\dfrac{b}{c+a}+\dfrac{c}{a+b}\geq \dfrac{3}{2}

方針

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

解答

abca\geq b\geq c の場合にのみ証明すればよい。

a+bc+ab+ca+b\geq c+a\geq b+c より,

1b+c1c+a1a+b\dfrac{1}{b+c}\geq \dfrac{1}{c+a}\geq \dfrac{1}{a+b}

よって並べ替えの不等式より,

ab+c+bc+a+ca+bbb+c+cc+a+aa+bab+c+bc+a+ca+bcb+c+ac+a+ba+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 を動かして全ての並べ替えを試した時に,i=1nxiyσ(i)\displaystyle\sum_{i=1}^nx_iy_{\sigma(i)} が最大となるのが σ(i)=i\sigma(i)=i (恒等変換)であることを示せばよいです。

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

証明

σ(1)=i1\sigma(1)=i\neq 1 のとき σ(j)=1\sigma(j)=1 となる 11 でない jj が存在する。

(x1xj)(y1yi)0(x_1-x_j)(y_1-y_i)\geq 0 より,

x1y1+xjyix1yi+xjy1x_1y_1+x_jy_i\geq x_1y_i+x_jy_1

つまり

x1yσ(j)+xjyσ(1)x1yσ(1)+xjyσ(j)x_1y_{\sigma(j)}+x_jy_{\sigma(1)}\geq x_1y_{\sigma(1)}+x_jy_{\sigma(j)}

よって,yσ(1)y_{\sigma(1)}yσ(j)y_{\sigma(j)} を交換しても(すなわち x1x_1 の相方と xjx_j の相方を交換しても)値は小さくならない。よって,最大の値となる並べ替え(の1つ)を σ\sigma' とおくと,σ(1)=1\sigma'(1)=1 を満たす。つまり,x1x_1 の相方は yσ(j)=y1y_{\sigma(j)}=y_1 の方がよいということ!

同様にして最大の値をとる並べ替え(の1つ)σ\sigma' は,任意の ii に対して σ(i)=i\sigma'(i)=i を満たすことが分かる。

つまり,i=1nxiyii=1nxiyσ(i)\displaystyle\sum_{i=1}^nx_iy_i\geq\sum_{i=1}^nx_iy_{\sigma(i)}

次に,yiy_i を逆方向から並べ替えて,

ynyn1y1-y_n\geq -y_{n-1}\geq\cdots\geq -y_1 としたものに上記で示した不等式を適用する:

i=1nxi(yni+1)i=1nxi(yσ(i))\displaystyle\sum_{i=1}^nx_i(-y_{n-i+1})\geq\sum_{i=1}^nx_i(-y_{\sigma(i)})

これより右側の不等式を得る:

i=1nxiyσ(i)i=1nxiyni+1\displaystyle\sum_{i=1}^nx_iy_{\sigma(i)}\geq\sum_{i=1}^nx_iy_{n-i+1}

ごちゃごちゃしていますが,要は「恒等変換以外は交換して値を改善できる」というわけです。

  1. 高校数学の美しい物語
  2. 並べ替え不等式の証明と例題