2014/04/01

チェビシェフの不等式の2通りの証明と例題

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

チェビシェフの不等式(Chebyshev’s sum inequality):
$x_1\geq x_2\geq\cdots\geq x_n\\y_1\geq y_2\geq\cdots \geq y_n$,
に対して,
$\dfrac{1}{n}\displaystyle\sum_{i=1}^nx_iy_i\geq(\dfrac{1}{n}\sum_{i=1}^nx_i)(\dfrac{1}{n}\sum_{i=1}^ny_i)\geq\dfrac{1}{n}\sum_{i=1}^nx_iy_{n+1-i}$


注:チェビシェフの不等式は二つあります。確率論におけるチェビシェフの不等式はマルコフの不等式とその証明のページ下部を参照してください。

チェビシェフの不等式は並べ替え不等式のよく使う特殊な形です。数学オリンピックの不等式証明問題では重要な武器になります。入試問題でも知っていると有利になることもまれにあります。

式よりもイメージで覚えましょう。「大きい物どうしの積の和は大きい」というイメージは並べ替え不等式と全く同じです。→並べ替え不等式の証明と例題

より詳しくいうと,「大きい物どうしの積の平均 $\geq$ 平均の積 $\geq$ 逆順の積の平均」となります。

このページではチェビシェフの不等式の証明を2通りの紹介します。
1:両辺の差を取って直接示す方法
2:並べ替え不等式を用いる方法

チェビシェフの不等式の証明1

方針:両辺の差が非負であることを示すのが不等式の最も基本的な証明方法です。 $n^2\times$ ((左辺)ー(中辺))
$=\displaystyle\sum_{i=1}^nnx_iy_i-\sum_{i=1}^n\sum_{j=1}^nx_iy_j\\
=\displaystyle\sum_{i=1}^n\sum_{j=1}^nx_iy_i-\sum_{i=1}^n\sum_{j=1}^nx_iy_j$
まではごく自然だと思いますがここで行き詰まります。そこで, $i, j$ の対称性を保つことを考えて一工夫します。

証明

$x_i-x_j$ と $y_i-y_j$ は同符号なので,
$\displaystyle\sum_{i=1}^n\sum_{j=1}^n(x_i-x_j)(y_i-y_j)\geq 0$
となる。あとはこれを変形していく:
$\displaystyle\sum_{i=1}^n\sum_{j=1}^n(x_iy_i+x_jy_j)\geq \sum_{i=1}^n\sum_{j=1}^n(x_iy_j+x_jy_i)\\
2n\displaystyle\sum_{i=1}^nx_iy_i\geq 2\sum_{i=1}^n\sum_{j=1}^nx_iy_j$
両辺を $2n^2$ で割ってチェビシェフの不等式を得る。
右側の不等式も同様。

シグマ計算がよくわからない人はこちらの2重和の説明を参考にしてみてください(→シグマ計算を機械的に行うための3つの公式

チェビシェフの不等式の証明2

方針:並べ替え不等式の特殊な場合なので並べ替え不等式を使って証明できるはずです。

証明

並べ替え不等式より以下の $n$ 個の不等式が成立する:
$\displaystyle\sum_{i=1}^nx_iy_i\geq x_1y_1+x_2y_2+\cdots +x_ny_n\\
\displaystyle\sum_{i=1}^nx_iy_i\geq x_1y_2+x_2y_3+\cdots +x_ny_1\\
\displaystyle\sum_{i=1}^nx_iy_i\geq x_1y_3+x_2y_4+\cdots +x_ny_2\\
\:\:\vdots$
これらを全て足しあわせて $n^2$ で割るとチェビシェフの不等式が得られる。

例題

以下の問題は1987年のIMOの問題候補をちょっと変えたものです。

問題

$a, b, c>0$ のとき以下の不等式を示せ:
$\dfrac{a^n}{b+c}+\dfrac{b^n}{c+a}+\dfrac{c^n}{a+b}\geq \dfrac{1}{2}(a^{n-1}+b^{n-1}+c^{n-1})$

方針:対称式の証明は大小関係を自由に決めて並べ替え不等式やチェビシェフの不等式を使うことができます。分母の形からNesbittの不等式を思いだしてほしいところです。

証明

対称式なので,$a\geq b\geq c$ の場合を証明すれば十分。このとき $\dfrac{1}{b+c}\geq\dfrac{1}{c+a}\geq\dfrac{1}{a+b}$ なので,チェビシェフの不等式より,
$\dfrac{a^n}{b+c}+\dfrac{b^n}{c+a}+\dfrac{c^n}{a+b}\\
\geq\dfrac{1}{3}(a^{n-1}+b^{n-1}+c^{n-1})(\dfrac{a}{b+c}+\dfrac{b}{c+a}+\dfrac{c}{a+b})$
これと,Nesbittの不等式
$\dfrac{a}{b+c}+\dfrac{b}{c+a}+\dfrac{c}{a+b}\geq\dfrac{3}{2}$ を組み合わせて求める不等式を得る。

Muirheadも並べ替えもチェビシェフも結局は「大きい物どうしの積の和は大きい」

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

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