文献あり

n-1EV :(

1760

この記事は,正確性を保証できません.ご注意ください.

はじめに

こんにちは.今回も不等式ですが,今回は $使える$ テクニックです.
紹介するのは,「n-1EV」または「n-1 Equal Value Principle」と呼ばれているものです.
軽く説明すると,ある多変数の式の最小値や最大値を考える時にある一変数の式を考えるだけで良くなります.もちろん我々は多変数より一変数のほうが扱いやすいですよね.なのでかなり嬉しい主張です！！
しかし注意が必要です.微分などの計算量が普通より多くなります.

前提知識

凸関数や凹関数の基礎
変曲点
微分の基礎

ちょっとした準備

優数列

$a = (a_{1}, a_{2}, \dots, a_{n}) \in R^{n}, b = (b_{1}, b_{2}, \dots, b_{n}) \in R^{n}$ は非増加な数列であるとする. $a ≻ b$ であるとは,以下の2つをみたすことを言う.

全ての $1 \leq k < n に対して,$ $\sum_{i = 1}^{k} a_{i} \geq \sum_{i = 1}^{k} b_{i}$ .
$\sum_{i = 1}^{n} a_{i} = \sum_{i = 1}^{n} b_{i}$ .

$a ≻ b$ であることを,「 $a$ は $b$ の優数列である」といい

Karamataの不等式

$f : R \to R$ は区間 $I \subset R$ で凸であるとし,非増加な2つの数列, $a = (a_{1}, a_{2}, \dots, a_{n}), b = (b_{1}, b_{2}, \dots, b_{n})$ は, $a_{i}, b_{i} \in I (i = 1, 2, \dots, n)$ と $a ≻ b$ をみたす.このとき,
$f (a_{1}) + f (a_{2}) + \dots + f (a_{n}) \geq f (b_{1}) + f (b_{2}) + \dots + f (b_{n})$
が成り立つ.

$f$ が凹なら, $- f$ は凸であるから,不等号はひっくり返る.

この不等式は証明を省きます.
証明を知りたい方は, こちらを参考にするとよいでしょう.
※追記　この先は狭義凸,凹のみ考えます.また,その時の等号成立条件は $a = b$ (全ての項がそれぞれ等しい)です.

$n - 1$ EV

では本題に行きましょう.

n - 1

$a_{1}, a_{2}, \dots, a_{n}$ は実数で, $a_{1} + a_{2} + \dots + a_{n} = S$ は一定であるものとし, $f : R \to R$ は一つだけ変曲点を有しているものとする.このとき,
$f (a_{1}) + f (a_{2}) + \dots + f (a_{n})$
が最大値または最小値をとるとき, $n - 1$ 個の $a_{i}$ は等しい.

$n - 1$ EVは変数が $R$ 全体を動くときのみ成り立つが,そうでないときにも成り立つことがあります.
詳しくはこの動画を見てください.

※追記　上限,下限でも成り立ちます

証明

$f (x)$ の変曲点を $k$ とおく. $x \geq k$ のとき, $f (x)$ が凸となるときの最大値の場合について考える.
まずは,全てが $k$ 以下にならないとき, $a_{1} \geq a_{2} \geq \dots \geq a_{l} \geq k \geq a_{l + 1} \geq \dots \geq a_{n}$ として一般性を失わない.
まず,Karamataの不等式より以下の二つの不等式が成り立つ.
$\sum_{i = 1}^{l} f (a_{i}) \leq (l - 1) f (k) + f (a_{1} + \dots + a_{l} - (l - 1) k) (l - 1) f (k) + \sum_{i = l + 1}^{n} f (a_{i}) \leq (n - 1) f (\frac{(l - 1) k + a_{l + 1} + \dots + a_{n}}{n - 1})$
これらより,
$\sum_{i = 1}^{n} f (a_{i}) \leq f (a_{1} + \dots + a_{l} - (l - 1)) + (n - 1) f (\frac{(l - 1) k + a_{l + 1} + \dots + a_{n}}{n - 1})$
が成り立つ.ここで, $X = \frac{(l - 1) k + a_{l + 1} + \dots + a_{n}}{n - 1}$ とおけば, $a_{1} + \dots + a_{l} - (l - 1) k = S - (n - 1) X$ であり,
${\sum_{i = 1}^{n} f (a_{i}) | a_{i} \in R, a_{1} + a_{2} + \dots + a_{n} = S} \supset {f (S - (n - 1) X) + (n - 1) f (X) | X \leq k} = {f (a_{1} + \dots + a_{l} - (l - 1) k) + (n - 1) f (\frac{(l - 1) k + a_{l + 1} + \dots + a_{n}}{n - 1}) | a_{i} \in R, a_{1} + a_{2} + \dots + a_{n} = S}$
をみたす.
よって, $\sum_{i = 1}^{n} f (a_{i})$ が最大値をとる時、
$\sum_{i = 1}^{n} f (a_{i}) = f (S - (n - 1) X) + (n - 1) f (X)$
が成り立ち,これは $n - 1$ 個の $a_{i}$ が等しいことを意味する.

$k \geq a_{1} \geq a_{2} \geq \dots \geq a_{n}$ であるとき,Karamataの不等式より,
$\sum_{i = 1}^{n} f (a_{i}) \leq n f (\frac{S}{n})$
が成り立ち, $n - 1$ 個の $a_{i}$ が等しいことを意味する.
以上より, $x \geq k$ のとき, $f (x)$ が凸となるときの最大値をとる場合は示された.
その他の場合は,同様に示される.

これだけではよくわからないと思いますので,例題を解いて慣れていきましょう.

IMO 2001

$a, b, c$ は正数である.
$\frac{a}{\sqrt{a^{2} + 8 b c}} + \frac{b}{\sqrt{b^{2} + 8 c a}} + \frac{c}{\sqrt{c^{2} + 8 a b}} \geq 1$
を示せ.

出典はこちら .

解答

$e^{x} = \frac{b c}{a^{2}}, e^{y} = \frac{c a}{b^{2}}, e^{z} = \frac{a b}{c^{2}}$ とおけば, $x + y + z = 0$ の下で,
$\frac{1}{\sqrt{1 + 8 e^{x}}} + \frac{1}{\sqrt{1 + 8 e^{y}}} + \frac{1}{\sqrt{1 + 8 e^{z}}} \geq 1$
を示せばよい.
$f (x) = \frac{1}{\sqrt{1 + 8 e^{x}}}$ とおけば,
$f (x) + f (y) + f (z) \geq 1$
となる.ここで,
$f^{″} (x) = \frac{4 e^{x} (4 e^{x} - 1)}{(1 + 8 e^{x})^{\frac{5}{2}}}$
であるから $f$ は1つだけ変曲点を有する.よって, $n - 1$ EVより, $0 < t$ に対して,
$\frac{2}{\sqrt{1 + 8 t}} + \frac{t}{\sqrt{t + 8}} \geq 1$
を示せばよい.後は単純な計算なので省く

Vietnam 1998

正数 $x_{1}, x_{2}, \dots, x_{n}$ は $\sum_{i = 1}^{n} \frac{1}{1998 + x_{i}} = \frac{1}{1998}$ をみたす.
$\frac{\sqrt[n]{x_{1} x_{2} \dots x_{n}}}{n - 1} \geq 1998$
を示せ.

出典はこちら .

解答

$y_{i} = \frac{1998}{1998 + x_{i}}$ とおけば, $\sum_{i = 1}^{n} y_{i} = 1$ の条件の下で,
$\prod_{i = 1}^{n} (\frac{1}{y_{i}} - 1) \geq (n - 1)^{n}$
を示せばよい.
両辺 $\log$ をとって, $f (x) = \log (\frac{1}{x} - 1)$ とおくと,
$f (y_{1}) + f (y_{2}) + \dots + f (y_{n}) \geq n f (\frac{1}{n})$
となる.ここで,
$f^{″} (x) = \frac{1 - 2 x}{(x^{2} - x)^{2}}$
であるから $f$ は1つだけ変曲点を有する.よって $n - 1$ EVより, $0 < t < 1$ に対して,
$(n - 1) \log (\frac{1}{t} - 1) + \log (\frac{1}{1 - (n - 1) t} - 1) \geq n \log (n - 1)$
を示せばよい.あとは単純な計算なので省く.

ネタバレありの感想

$f (y_{1}) + f (y_{2}) + \dots + f (y_{n}) \geq n f (\frac{1}{n})$
を示すときにもし,考える範囲で常に凸なら,Karamataの不等式により一発で解けます.
変曲点が $\frac{1}{2}$ でなんとなくで成り立ちそうだなともあまり感じれません.そう考えると $n - 1$ EVは最小値が与えられていなくても解ける万能なテクニックなようにも感じられますね.

おわりに

最後まで見ていただきありがとうございました.
実はこの主張は,凸(resp. 凹)なら端点で最大値(resp. 最小値)をとるなどのことをふまえれば,ほんのちょっとだけ当たり前な意味にみえます.( $R$ でしかなかなか使えないことも)

できるだけ丁寧に取り扱ったつもりですがわかりにくいところが多いかもしれません.
この記事を書く上で参考にした文献が母国語ではないためかなり理解がしずらかったと感じています.
この記事は,正確性を保証できませんのでご参考までに.
怖いので,いっぱい保険をかけておきます.
それでは,ありがとうございました.