1 並べ替え不等式 例 1.1. a = ( 1 , 2 , 3 ) a=(1,2,3) a = ( 1 , 2 , 3 ) b = ( 4 , 5 , 6 ) b=(4,5,6) b = ( 4 , 5 , 6 ) b b b
( 4 , 5 , 6 ) 32 ( 4 , 6 , 5 ) 31 ( 5 , 4 , 6 ) 31 ( 5 , 6 , 4 ) 29 ( 6 , 4 , 5 ) 29 ( 6 , 5 , 4 ) 28 \begin{array}{c|c}
(4,5,6)&32\\
(4,6,5)&31\\
(5,4,6)&31\\
(5,6,4)&29\\
(6,4,5)&29\\
(6,5,4)&28
\end{array} ( 4 , 5 , 6 ) ( 4 , 6 , 5 ) ( 5 , 4 , 6 ) ( 5 , 6 , 4 ) ( 6 , 4 , 5 ) ( 6 , 5 , 4 ) 32 31 31 29 29 28 となる。同じ順に並べた場合が最大であり、逆順に並べた場合が最小である。
定理 1.2 (並べ替え不等式). n ≥ 2 n\ge2 n ≥ 2
a 1 ≤ a 2 ≤ ⋯ ≤ a n , b 1 ≤ b 2 ≤ ⋯ ≤ b n a_1\le a_2\le\cdots\le a_n,\qquad
b_1\le b_2\le\cdots\le b_n a 1 ≤ a 2 ≤ ⋯ ≤ a n , b 1 ≤ b 2 ≤ ⋯ ≤ b n を満たすとする。σ \sigma σ { 1 , 2 , … , n } \{1,2,\ldots,n\} { 1 , 2 , … , n }
∑ i = 1 n a i b n + 1 − i ≤ ∑ i = 1 n a i b σ ( i ) ≤ ∑ i = 1 n a i b i \sum_{i=1}^{n}a_ib_{n+1-i}
\le
\sum_{i=1}^{n}a_ib_{\sigma(i)}
\le
\sum_{i=1}^{n}a_ib_i i = 1 ∑ n a i b n + 1 − i ≤ i = 1 ∑ n a i b σ ( i ) ≤ i = 1 ∑ n a i b i が成り立つ。
二列がともに狭義単調増加である場合、右側の等号はσ ( i ) = i \sigma(i)=i σ ( i ) = i i i i σ ( i ) = n + 1 − i \sigma(i)=n+1-i σ ( i ) = n + 1 − i i i i
証明. c i = b σ ( i ) c_i=b_{\sigma(i)} c i = b σ ( i ) ( c 1 , … , c n ) (c_1,\ldots,c_n) ( c 1 , … , c n )
N = # { ( k , l ) ∣ 1 ≤ k < l ≤ n , c k > c l } N=\#\{(k,l)\mid 1\le k<l\le n,\ c_k>c_l\} N = # {( k , l ) ∣ 1 ≤ k < l ≤ n , c k > c l } とする。N > 0 N>0 N > 0 c i > c i + 1 c_i>c_{i+1} c i > c i + 1 σ ′ \sigma' σ ′
∑ k = 1 n a k b σ ′ ( k ) − ∑ k = 1 n a k b σ ( k ) = ( a i + 1 − a i ) ( c i − c i + 1 ) ≥ 0 \sum_{k=1}^{n}a_kb_{\sigma'(k)}-
\sum_{k=1}^{n}a_kb_{\sigma(k)}
=(a_{i+1}-a_i)(c_i-c_{i+1})\ge0 k = 1 ∑ n a k b σ ′ ( k ) − k = 1 ∑ n a k b σ ( k ) = ( a i + 1 − a i ) ( c i − c i + 1 ) ≥ 0 である。同時に逆転数は一つ減る。逆転数は非負整数であるから、有限回の交換で逆転数は0 0 0 ( c 1 , … , c n ) (c_1,\ldots,c_n) ( c 1 , … , c n ) 0 0 0 ( b 1 , … , b n ) (b_1,\ldots,b_n) ( b 1 , … , b n )
∑ i = 1 n a i b σ ( i ) ≤ ∑ i = 1 n a i b i \sum_{i=1}^{n}a_ib_{\sigma(i)}\le\sum_{i=1}^{n}a_ib_i i = 1 ∑ n a i b σ ( i ) ≤ i = 1 ∑ n a i b i を得る。
c j = − b n + 1 − j c_j=-b_{n+1-j} c j = − b n + 1 − j c 1 ≤ ⋯ ≤ c n c_1\le\cdots\le c_n c 1 ≤ ⋯ ≤ c n τ ( i ) = n + 1 − σ ( i ) \tau(i)=n+1-\sigma(i) τ ( i ) = n + 1 − σ ( i ) τ \tau τ ( a i ) (a_i) ( a i ) ( c i ) (c_i) ( c i )
∑ i = 1 n a i ( − b σ ( i ) ) ≤ ∑ i = 1 n a i ( − b n + 1 − i ) \sum_{i=1}^{n}a_i(-b_{\sigma(i)})
\le
\sum_{i=1}^{n}a_i(-b_{n+1-i}) i = 1 ∑ n a i ( − b σ ( i ) ) ≤ i = 1 ∑ n a i ( − b n + 1 − i ) となる。両辺に− 1 -1 − 1
二列がともに狭義単調増加であるとする。右側の並びが恒等置換でなければ逆転が存在し、各交換についてa i + 1 − a i > 0 a_{i+1}-a_i>0 a i + 1 − a i > 0 c i − c i + 1 > 0 c_i-c_{i+1}>0 c i − c i + 1 > 0 ( − b n , … , − b 1 ) (-b_n,\ldots,-b_1) ( − b n , … , − b 1 ) 0 0 0 ▨
2 多変数の相加平均と相乗平均 二変数の場合は「不等式の証明」で示した関係を出発点にし、項数が一般の場合へ広げます。
定理 2.1. n ≥ 2 n\ge2 n ≥ 2 x 1 , … , x n x_1,\ldots,x_n x 1 , … , x n
x 1 + x 2 + ⋯ + x n n ≥ x 1 x 2 ⋯ x n n \frac{x_1+x_2+\cdots+x_n}{n}
\ge
\sqrt[n]{x_1x_2\cdots x_n} n x 1 + x 2 + ⋯ + x n ≥ n x 1 x 2 ⋯ x n が成り立つ。積が0 0 0 0 0 0 x 1 = x 2 = ⋯ = x n x_1=x_2=\cdots=x_n x 1 = x 2 = ⋯ = x n
証明. 上の主張をP ( n ) P(n) P ( n ) x 1 , x 2 x_1,x_2 x 1 , x 2
x 1 + x 2 2 − x 1 x 2 = ( x 1 − x 2 ) 2 2 ≥ 0 \frac{x_1+x_2}{2}-\sqrt{x_1x_2}
=\frac{(\sqrt{x_1}-\sqrt{x_2})^2}{2}\ge0 2 x 1 + x 2 − x 1 x 2 = 2 ( x 1 − x 2 ) 2 ≥ 0 であるからP ( 2 ) P(2) P ( 2 ) x 1 = x 2 x_1=x_2 x 1 = x 2
P ( n ) P(n) P ( n ) x 1 , … , x 2 n x_1,\ldots,x_{2n} x 1 , … , x 2 n
A = x 1 ⋯ x n n , B = x n + 1 ⋯ x 2 n n A=\sqrt[n]{x_1\cdots x_n},\qquad
B=\sqrt[n]{x_{n+1}\cdots x_{2n}} A = n x 1 ⋯ x n , B = n x n + 1 ⋯ x 2 n と置く。P ( n ) P(n) P ( n ) P ( 2 ) P(2) P ( 2 ) A , B A,B A , B
x 1 + ⋯ + x 2 n 2 n = 1 2 ( x 1 + ⋯ + x n n + x n + 1 + ⋯ + x 2 n n ) ≥ A + B 2 ≥ A B = x 1 x 2 ⋯ x 2 n 2 n \begin{aligned}
\frac{x_1+\cdots+x_{2n}}{2n}
&=\frac12\left(\frac{x_1+\cdots+x_n}{n}
+\frac{x_{n+1}+\cdots+x_{2n}}{n}\right)\\
&\ge\frac{A+B}{2}
\ge\sqrt{AB}
=\sqrt[2n]{x_1x_2\cdots x_{2n}}
\end{aligned} 2 n x 1 + ⋯ + x 2 n = 2 1 ( n x 1 + ⋯ + x n + n x n + 1 + ⋯ + x 2 n ) ≥ 2 A + B ≥ A B = 2 n x 1 x 2 ⋯ x 2 n となる。二つの不等式で同時に等号が成り立つのは、前半と後半の各項がそれぞれ等しく、さらにA = B A=B A = B P ( 2 n ) P(2n) P ( 2 n ) x 1 = ⋯ = x 2 n x_1=\cdots=x_{2n} x 1 = ⋯ = x 2 n
n ≥ 3 n\ge3 n ≥ 3 P ( n ) P(n) P ( n ) x 1 , … , x n − 1 x_1,\ldots,x_{n-1} x 1 , … , x n − 1
A = x 1 + ⋯ + x n − 1 n − 1 A=\frac{x_1+\cdots+x_{n-1}}{n-1} A = n − 1 x 1 + ⋯ + x n − 1 と置く。A = 0 A=0 A = 0 x i x_i x i 0 0 0 P ( n − 1 ) P(n-1) P ( n − 1 ) A > 0 A>0 A > 0 x n = A x_n=A x n = A P ( n ) P(n) P ( n )
A ≥ x 1 ⋯ x n − 1 A n A\ge\sqrt[n]{x_1\cdots x_{n-1}A} A ≥ n x 1 ⋯ x n − 1 A を得る。両辺は非負であるからn n n
A n ≥ x 1 ⋯ x n − 1 A A^n\ge x_1\cdots x_{n-1}A A n ≥ x 1 ⋯ x n − 1 A となる。正の数A A A
A n − 1 ≥ x 1 ⋯ x n − 1 A^{n-1}\ge x_1\cdots x_{n-1} A n − 1 ≥ x 1 ⋯ x n − 1 であり、非負のn − 1 n-1 n − 1 P ( n − 1 ) P(n-1) P ( n − 1 ) P ( n ) P(n) P ( n ) x 1 , … , x n − 1 , A x_1,\ldots,x_{n-1},A x 1 , … , x n − 1 , A x 1 = ⋯ = x n − 1 x_1=\cdots=x_{n-1} x 1 = ⋯ = x n − 1
P ( 2 ) P(2) P ( 2 ) P ( 4 ) , P ( 8 ) , … P(4),P(8),\ldots P ( 4 ) , P ( 8 ) , … n ≥ 2 n\ge2 n ≥ 2 n ≤ 2 k n\le2^k n ≤ 2 k k k k P ( 2 k ) P(2^k) P ( 2 k ) 2 k − n 2^k-n 2 k − n P ( n ) P(n) P ( n ) n n n ▨
3 一般項数のコーシー・シュワルツの不等式 定理 3.1. n ≥ 2 n\ge2 n ≥ 2 x 1 , … , x n , y 1 , … , y n x_1,\ldots,x_n,y_1,\ldots,y_n x 1 , … , x n , y 1 , … , y n
( ∑ i = 1 n x i 2 ) ( ∑ i = 1 n y i 2 ) ≥ ( ∑ i = 1 n x i y i ) 2 \left(\sum_{i=1}^{n}x_i^2\right)
\left(\sum_{i=1}^{n}y_i^2\right)
\ge
\left(\sum_{i=1}^{n}x_iy_i\right)^2 ( i = 1 ∑ n x i 2 ) ( i = 1 ∑ n y i 2 ) ≥ ( i = 1 ∑ n x i y i ) 2 が成り立つ。等号が成り立つのは、すべてのx i x_i x i 0 0 0 t t t i i i y i = t x i y_i=tx_i y i = t x i
証明.
X = ∑ i = 1 n x i 2 , Y = ∑ i = 1 n y i 2 , Z = ∑ i = 1 n x i y i X=\sum_{i=1}^{n}x_i^2,\qquad
Y=\sum_{i=1}^{n}y_i^2,\qquad
Z=\sum_{i=1}^{n}x_iy_i X = i = 1 ∑ n x i 2 , Y = i = 1 ∑ n y i 2 , Z = i = 1 ∑ n x i y i と置く。X = 0 X=0 X = 0 x i x_i x i 0 0 0 Z = 0 Z=0 Z = 0 0 0 0
X > 0 X>0 X > 0 t t t
f ( t ) = ∑ i = 1 n ( t x i − y i ) 2 = X t 2 − 2 Z t + Y ≥ 0 f(t)=\sum_{i=1}^{n}(tx_i-y_i)^2=Xt^2-2Zt+Y\ge0 f ( t ) = i = 1 ∑ n ( t x i − y i ) 2 = X t 2 − 2 Z t + Y ≥ 0 である。「2次不等式」で示した判別式の条件により、この2次式の判別式は0 0 0
( − 2 Z ) 2 − 4 X Y ≤ 0 (-2Z)^2-4XY\le0 ( − 2 Z ) 2 − 4 X Y ≤ 0 となり、Z 2 ≤ X Y Z^2\le XY Z 2 ≤ X Y
X > 0 X>0 X > 0 Z 2 = X Y Z^2=XY Z 2 = X Y f f f 0 0 0 t 0 = Z / X t_0=Z/X t 0 = Z / X
0 = f ( t 0 ) = ∑ i = 1 n ( t 0 x i − y i ) 2 0=f(t_0)=\sum_{i=1}^{n}(t_0x_i-y_i)^2 0 = f ( t 0 ) = i = 1 ∑ n ( t 0 x i − y i ) 2 であり、各平方項が0 0 0 y i = t 0 x i y_i=t_0x_i y i = t 0 x i i i i t t t y i = t x i y_i=tx_i y i = t x i i i i Y = t 2 X , Z = t X Y=t^2X,Z=tX Y = t 2 X , Z = tX Z 2 = X Y Z^2=XY Z 2 = X Y ▨
4 分数の形 定理 4.1. n ≥ 2 n\ge2 n ≥ 2 a 1 , … , a n a_1,\ldots,a_n a 1 , … , a n b 1 , … , b n b_1,\ldots,b_n b 1 , … , b n
∑ i = 1 n a i 2 b i ≥ ( ∑ i = 1 n a i ) 2 ∑ i = 1 n b i \sum_{i=1}^{n}\frac{a_i^2}{b_i}
\ge
\frac{\left(\sum_{i=1}^{n}a_i\right)^2}{\sum_{i=1}^{n}b_i} i = 1 ∑ n b i a i 2 ≥ ∑ i = 1 n b i ( ∑ i = 1 n a i ) 2 が成り立つ。等号が成り立つことと、a 1 / b 1 , … , a n / b n a_1/b_1,\ldots,a_n/b_n a 1 / b 1 , … , a n / b n
証明. 各b i > 0 b_i>0 b i > 0 b i \sqrt{b_i} b i
x i = a i b i , y i = b i x_i=\frac{a_i}{\sqrt{b_i}},\qquad y_i=\sqrt{b_i} x i = b i a i , y i = b i と置くことができる。定理 3.1 へ代入すると
( ∑ i = 1 n a i 2 b i ) ( ∑ i = 1 n b i ) ≥ ( ∑ i = 1 n a i ) 2 \left(\sum_{i=1}^{n}\frac{a_i^2}{b_i}\right)
\left(\sum_{i=1}^{n}b_i\right)
\ge
\left(\sum_{i=1}^{n}a_i\right)^2 ( i = 1 ∑ n b i a i 2 ) ( i = 1 ∑ n b i ) ≥ ( i = 1 ∑ n a i ) 2 となる。∑ b i > 0 \sum b_i>0 ∑ b i > 0
すべてのa i a_i a i 0 0 0 a i / b i a_i/b_i a i / b i 0 0 0 a i a_i a i 0 0 0 定理 3.1 の等号条件は、あるt ≠ 0 t\ne0 t = 0
b i = t a i b i \sqrt{b_i}=t\frac{a_i}{\sqrt{b_i}} b i = t b i a i がすべてのi i i a i / b i = 1 / t a_i/b_i=1/t a i / b i = 1/ t
逆にa i / b i a_i/b_i a i / b i k k k k = 0 k=0 k = 0 a i a_i a i 0 0 0 k ≠ 0 k\ne0 k = 0
b i = 1 k a i b i \sqrt{b_i}=\frac1k\frac{a_i}{\sqrt{b_i}} b i = k 1 b i a i がすべてのi i i 定理 3.1 の等号条件を満たす。したがって等号条件の双方向が成り立つ。▨
例 4.2. 正の実数a , b , c a,b,c a , b , c 定理 4.1 を適用すると
a 2 b + b 2 c + c 2 a ≥ ( a + b + c ) 2 b + c + a = a + b + c \frac{a^2}{b}+\frac{b^2}{c}+\frac{c^2}{a}
\ge
\frac{(a+b+c)^2}{b+c+a}=a+b+c b a 2 + c b 2 + a c 2 ≥ b + c + a ( a + b + c ) 2 = a + b + c を得る。等号が成り立つのは
a b = b c = c a \frac ab=\frac bc=\frac ca b a = c b = a c の場合に限る。この共通値をk k k k > 0 k>0 k > 0
k 3 = a b b c c a = 1 k^3=\frac ab\frac bc\frac ca=1 k 3 = b a c b a c = 1 であるからk = 1 k=1 k = 1 a = b = c a=b=c a = b = c a = b = c a=b=c a = b = c
5 凸性による考え方 区間上で定義された関数について、グラフ上の任意の二点を結ぶ線分が、その二点の間でグラフより下に来ないとき、その関数を下に凸であるといいます。「その二点の間」という条件は外すことができません。線分を区間の外へ延長すると、下に凸な関数でも直線がグラフの下へ回る場合があります。一次関数のように線分がグラフと重なる場合も、下に凸な関数に含めます。
下に凸な関数では、数の重み付き平均を先に取ってから関数へ入れた値が、各数を関数へ入れてから重み付き平均を取った値以下になります。多変数の相加平均と相乗平均の関係を、この見方から導くこともできます。本記事は凸性による証明を扱わず、関数の凹凸と競技数学への応用は後続の記事へ委ねます。
6 つまずいたら
並べ替え不等式では、二列をともに小さい順へ並べます。同じ順が最大、逆順が最小であることは、三項の数値例で確認することができます。
多変数の相加平均と相乗平均の関係は、非負実数についての主張です。x 1 = x 2 = − 1 x_1=x_2=-1 x 1 = x 2 = − 1 − 1 -1 − 1 1 1 1
分数の形では、分母に置く数がすべて正であることを確かめます。a 1 = 1 , a 2 = 3 , b 1 = 4 , b 2 = − 1 a_1=1,a_2=3,b_1=4,b_2=-1 a 1 = 1 , a 2 = 3 , b 1 = 4 , b 2 = − 1 − 8.75 -8.75 − 8.75 16 / 3 16/3 16/3
複数の評価をつなぐ場合は、各段階の等号条件が同時に成り立つかを確かめます。一段階だけの等号条件から全体の等号条件を決めることはできません。
7 演習 問題 7.1. 実数列a = ( 1 , 2 , 4 ) a=(1,2,4) a = ( 1 , 2 , 4 ) b = ( 1 , 3 , 5 ) b=(1,3,5) b = ( 1 , 3 , 5 ) ∑ i = 1 3 a i b σ ( i ) \sum_{i=1}^{3}a_ib_{\sigma(i)} ∑ i = 1 3 a i b σ ( i ) σ \sigma σ
解答. b b b
( 1 , 3 , 5 ) , ( 1 , 5 , 3 ) , ( 3 , 1 , 5 ) , ( 3 , 5 , 1 ) , ( 5 , 1 , 3 ) , ( 5 , 3 , 1 ) (1,3,5),(1,5,3),(3,1,5),(3,5,1),(5,1,3),(5,3,1) ( 1 , 3 , 5 ) , ( 1 , 5 , 3 ) , ( 3 , 1 , 5 ) , ( 3 , 5 , 1 ) , ( 5 , 1 , 3 ) , ( 5 , 3 , 1 ) の順に並べたとき、積の和はそれぞれ
27 , 23 , 25 , 17 , 19 , 15 27,23,25,17,19,15 27 , 23 , 25 , 17 , 19 , 15 となる。したがって最大値は同じ順に並べた場合の27 27 27 15 15 15 定理 1.2 の評価と一致する。▨
問題 7.2. 正の実数x 1 , … , x n x_1,\ldots,x_n x 1 , … , x n x 1 x 2 ⋯ x n = 1 x_1x_2\cdots x_n=1 x 1 x 2 ⋯ x n = 1 x 1 + x 2 + ⋯ + x n ≥ n x_1+x_2+\cdots+x_n\ge n x 1 + x 2 + ⋯ + x n ≥ n
解答. 定理 2.1 により
x 1 + ⋯ + x n n ≥ x 1 ⋯ x n n = 1 \frac{x_1+\cdots+x_n}{n}
\ge
\sqrt[n]{x_1\cdots x_n}=1 n x 1 + ⋯ + x n ≥ n x 1 ⋯ x n = 1 である。両辺に正の整数n n n x 1 + ⋯ + x n ≥ n x_1+\cdots+x_n\ge n x 1 + ⋯ + x n ≥ n x 1 = ⋯ = x n x_1=\cdots=x_n x 1 = ⋯ = x n 1 1 1 1 1 1 ▨
問題 7.3. 正の実数a , b , c a,b,c a , b , c
1 a + 1 b + 1 c ≥ 9 a + b + c \frac1a+\frac1b+\frac1c\ge\frac9{a+b+c} a 1 + b 1 + c 1 ≥ a + b + c 9 を分数の形のコーシー・シュワルツの不等式で示し、等号条件を求めよ。
解答. 定理 4.1 で分子を1 , 1 , 1 1,1,1 1 , 1 , 1 a , b , c a,b,c a , b , c
1 a + 1 b + 1 c ≥ ( 1 + 1 + 1 ) 2 a + b + c = 9 a + b + c \frac1a+\frac1b+\frac1c
\ge
\frac{(1+1+1)^2}{a+b+c}
=\frac9{a+b+c} a 1 + b 1 + c 1 ≥ a + b + c ( 1 + 1 + 1 ) 2 = a + b + c 9 を得る。等号が成り立つことと1 / a = 1 / b = 1 / c 1/a=1/b=1/c 1/ a = 1/ b = 1/ c a , b , c a,b,c a , b , c a = b = c a=b=c a = b = c ▨