2014/05/25

n変数の不等式証明のテクニック

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

数学オリンピックの不等式証明問題は $3$ 変数のものとn変数のものがほとんどです。

n変数の不等式証明

n変数の場合には3変数の場合に使える様々なテクニックが使えません。

この記事ではn変数の不等式を「数列の積の和とみなす」ことによって証明するテクニックを紹介します。

数列の積の和とみなすことで,並べ替え不等式チェビシェフの不等式アーベルの総和公式などが使えます。

数オリの問題に挑戦

1975年の国際数学オリンピックブルガリア大会の第1問です。数オリの問題の中ではかなり簡単な問題です。

問題1

実数 $x_i,y_i (i=1,2,\cdots,n)$ が $x_1\geq x_2\geq\cdots\geq x_n$ かつ,$y_1\geq y_2\geq\cdots\geq y_n$ を満たすとする。
$y_1,y_2,\cdots,y_n$ の任意の置換(並べ替え)$z_1,z_2,\cdots,z_n$ に対して以下の不等式が成立することを証明せよ。
$\displaystyle\sum_{i=1}^n(x_i-y_i)^2\leq\sum_{i=1}^n(x_i-z_i)^2$

方針:とりあえず展開してみると「数列の積の和」が出現します。並べ替え不等式で一発です。

解答

$\displaystyle\sum_{i=1}^ny_i^2=\sum_{i=1}^nz_i^2$ に注意して展開すると示すべき不等式は以下のようになる:
$\displaystyle\sum_{i=1}^nx_iy_i\geq\sum_{i=1}^nx_iz_i$
これは並べ替え不等式そのもの。

数オリの問題に挑戦part2

1978年国際数学オリンピックルーマニア大会の第5問です。

問題2

$a_n$ は全ての項が自然数で全て異なる数列とする。このとき以下の不等式を証明せよ:
$\displaystyle\sum_{k=1}^n\dfrac{a_k}{k^2}\geq\sum_{k=1}^n\dfrac{1}{k}$

方針1:左辺を数列の積の和と見ます。右辺は定数なので左辺の最小値を評価してやればよいわけです。 $\dfrac{1}{k^2}$ は減少数列なので,左辺は $a_k$ が増加数列のときに値が小さくなります。

解答1:
$n$ を固定して左辺がどのようなときに最小になるか考える。並べ替え不等式より,$a_k$ が増加数列のときだけを考えればよい。(そうでないときは並べ替えによって値をより小さくできる)よって,左辺が最小になるのは $a_1=1,a_2=2,\cdots,a_n=n$ のときで,そのときの値は右辺と一致する。


アーベルの総和公式を用いた別解も紹介しておきます。

方針2:アーベルの総和公式は「数列の積の和」を評価するのに使えます。 $A_k$ の評価以外は全て等式変形で証明できます。

解答2:
$\displaystyle\sum_{i=1}^ka_i=A_k$ とおくと,$A_k\geq\dfrac{k(k+1)}{2}$ であり,アーベルの総和公式より,
$\displaystyle\sum_{k=1}^n\dfrac{a_k}{k^2}=\dfrac{A_n}{n^2}-\displaystyle\sum_{k=1}^{n-1}A_k(\dfrac{1}{(k+1)^2}-\dfrac{1}{k^2})\\
\geq\displaystyle\dfrac{1}{n^2}\dfrac{n(n+1)}{2}+\sum_{k=1}^{n-1}\dfrac{k(k+1)}{2}\dfrac{2k+1}{k^2(k+1)^2}\\
=\dfrac{1}{2}(1+\dfrac{1}{n}+\displaystyle\sum_{k=1}^{n-1}(\dfrac{1}{k}+\dfrac{1}{k+1}))\\
=\displaystyle\sum_{k=1}^n\dfrac{1}{k}$

n変数の不等式だからといって必ずしも難問とは限りません。

Tag: 国際数学オリンピックの過去問

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