2014/05/28

Karamataの不等式

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

Karamataの不等式:

  • $[a]\succeq [b]$ を満たす実数の列 $a=(a_1, a_2,\cdots , a_n), b=(b_1, b_2,\cdots, b_n)$
  • $f(x)$ は微分可能で凸

このとき,
$f(a_1)+f(a_2)+\cdots +f(a_n)\geq f(b_1)+f(b_2)+\cdots +f(b_n)$

このページではKaramataの不等式の意味,応用例,証明を解説します。

Karamataの不等式の意味

まず,$[a]\succeq [b]$ というのは「2つの数列の全体の和が等しく,$a$ の方が $b$ より偏っている」というイメージです。
厳密な定義は以下の通りです:

項数が等しい非増加な数列 $a, b$ に対して $[a]\succeq[b]$ とは,
$\displaystyle\sum_{i=1}^{k}a_i\geq\sum_{i=1}^{k}b_i\:\:(k=1, 2, \cdots, n-1)$ かつ
$\displaystyle\sum_{i=1}^{n}a_n=\sum_{i=1}^{n}b_n$
が成立することを表す。

この記号に不慣れな方はMuirheadの不等式と具体例を参考にしてください。


次に,$f$ が凸というのは様々な定義がありますが,「下に出っ張っている」というイメージです。
凸関数の概念を知らない方はイェンゼンの不等式の3通りの証明を参考にしてください。


karamataの不等式のイメージ

以上を合わせると,Karamataの不等式は,「凸関数においては,$x$ 座標が偏っている図形の重心の方がより上に来る」ことを表しています。

例えば $n=2$ の場合,図において青丸の方が赤丸より上にあるということを表しています。直感的にはイメージしやすいですね。

Karamataの不等式の応用例

1996年のアジア太平洋数学オリンピック(APMO)の問題です。ルートの和とシュワルツの不等式でも紹介した問題です。Ravi変換を用いるのが定石ですがKaramataの不等式を用いることでエレガントに証明します。

問題

$a,b,c$ が三角形の辺の長さのとき以下の不等式を証明せよ:
$\sqrt{a+b-c}+\sqrt{b+c-a}+\sqrt{c+a-b}\leq\sqrt{a}+\sqrt{b}+\sqrt{c}$

方針:$f(A_1)+f(A_2)+f(A_3)\leq f(B_1)+f(B_2)+f(B_3)$ という形をしておりイカにもKaramataです。 $\sqrt{x}$ は上に凸な関数なので$-\sqrt{x}$ を考えることで強引に凸関数にします。

解答

対称式なので $a\geq b\geq c$ の場合を証明すればよい。
・簡単な計算により,
$(a+b-c,c+a-b,b+c-a)\succeq (a,b,c)$
が分かる。
・ $f(x)=-\sqrt{x}$ とおくと $f'(x)=\dfrac{-1}{2\sqrt{x}}$ が増加関数なので $f(x)$ は凸関数。
以上からKaramataの不等式が使える:
$-\sqrt{a+b-c}-\sqrt{b+c-a}-\sqrt{c+a-b}\geq -\sqrt{a}-\sqrt{b}-\sqrt{c}$
両辺を$-1$ 倍して与式を得る。

Karamataの不等式の証明

アーベルの総和公式を用います。
→アーベルの総和公式とその解釈

証明

$f(x)$ は凸関数なので,傾き $c_k=\dfrac{f(b_k)-f(a_k)}{b_k-a_k}$ は減少数列となる。($b_k=a_k$ の場合は微分係数 $f'(a_k)$ を $c_k$ とおく)
すると,アーベルの総和公式が使えて,
$\displaystyle\sum_{k=1}^n(f(a_k)-f(b_k))=\sum_{k=1}^nc_k(a_k-b_k)\\
=c_n(A_n-B_n)+\displaystyle\sum_{k=1}^{n-1}(c_k-c_{k+1})(A_k-B_k)\geq 0$
ただし,$A,B$ は数列 $a,b$ の部分和を表し,$[a]\succeq [b]$ より $A_k-B_k\geq 0$ であることを用いた。

Karamataはイェンゼンと同じく図形的にイメージしやすい不等式です

Tag: 各地の数オリの過去問

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