並べ替え不等式の意味と証明、具体例について
1. 並べ替え不等式とは
\[ \sum_{i=1}^n a_i b_i \geq \sum_{i=1}^n a_i b_{\sigma(i)} \geq \sum_{i=1}^n a_i b_{n+1-i} \]
この不等式のことを並べ替え不等式という。ここで、\(\sigma(i)\) は \(1, 2, \dots, n\) の任意の順列を表す置換です。\(\sigma\) によって、\(b_i\) の並び順が変わります。
この不等式を具体的に書くと次のようになります。
\[ a_1 b_1 + a_2 b_2 + \cdots + a_n b_n \geq a_1 b_{\sigma(1)} + a_2 b_{\sigma(2)} + \cdots + a_n b_{\sigma(n)}\geq a_1 b_n + a_2 b_{n-1} + \cdots + a_n b_1 \]
1.1. 置換とは
置換とは、ある集合の要素の並びを並べ替える操作のことです。置換は通常、記号 \(\sigma\) を使って表されます。ここでは、1から3の要素の置換について簡単に説明します。
1から3の要素を持つ集合 \(\{1, 2, 3\}\) の置換は、それらの要素を並べ替える方法を指します。この場合、すべての要素の並び替えを考えると、次の6つの置換が存在します。
- \(\sigma(1) = 1, \sigma(2) = 2, \sigma(3) = 3\) （元の順序）
- \(\sigma(1) = 1, \sigma(2) = 3, \sigma(3) = 2\)
- \(\sigma(1) = 2, \sigma(2) = 1, \sigma(3) = 3\)
- \(\sigma(1) = 2, \sigma(2) = 3, \sigma(3) = 1\)
- \(\sigma(1) = 3, \sigma(2) = 1, \sigma(3) = 2\)
- \(\sigma(1) = 3, \sigma(2) = 2, \sigma(3) = 1\)
1.2. 寿司を食べました
ある寿司屋で、どれだけのお勘定になるのかを並び替えの不等式を利用して見積もってみましょう。3種類のすしを食べて、値段は以下の通りとします。
- まぐろ：300円
- サーモン：250円
- かつお：200円
この値段を安い順に並べると
\[ a_1 = 200, \quad a_2 = 250, \quad a_3 = 300 \]
また、これらのすしを食べましたが、何をどれだけ食べたかは忘れてしまいました。ただし、食べた個数の順序は分かっており、食べた個数が多い順に
- 3個、2個、1個（どの種類を何個食べたかは不明）
とします。小さい順に並べると
\[ b_1 = 1, \quad b_2 = 2, \quad b_3 = 3 \]
ここで、すしの値段を \(a_1, a_2, a_3\) 、食べた個数を \(b_1, b_2, b_3\) とします。並び替えの不等式より、\(a_1 \leq a_2 \leq a_3\) かつ \(b_1 \leq b_2 \leq b_3\) の場合、つまり、値段が高いものを多く、安いものを少なく食べたとき、
\[ \sum_{i=1}^3 a_i b_i = 200 \times 1 + 250 \times 2 + 300 \times 3 = 200+ 500 + 900= 1600\]
逆に、値段が高いものを少なく、安いものを多く食べた場合（個数の順序が逆の場合）、つまり \(b_3, b_2, b_1\) で計算すると、
\[ \sum_{i=1}^3 a_i b_{4-i} = 200 \times 3 + 250 \times 2 + 300 \times 1 = 600 + 500 + 300= 1400\]
並び替えの不等式より、
\[ 1600 \geq \sum_{i=1}^3 a_i b_{\sigma(i)} \geq 1400 \]
つまり、たいたい1600円から1400円くらいの寿司を食べたことがわかります。
2. 数学的帰納法を利用した証明
2.1. 証明の方針
証明の方針を立ててみましょう。
$$S_n=a_1 b_1 + a_2 b_2 + \cdots + a_n b_n-(a_1 b_{\sigma(1)} + a_2 b_{\sigma(2)} + \cdots + a_n b_{\sigma(n)})$$
として、$S_n\geq 0$が成り立つことを示すことができたら、
\[ a_1 b_1 + a_2 b_2 + \cdots + a_n b_n \geq a_1 b_{\sigma(1)} + a_2 b_{\sigma(2)} + \cdots + a_n b_{\sigma(n)} \]
を示すことができるので、そこを数学的帰納法で攻めてみましょう。
2.2. 証明
まず、 $S_n$の\( n = 2 \) の場合を考えます。このとき、次の2つの積の差を考えます。
\[\begin{align*} &(a_1 b_1 + a_2 b_2) – (a_1 b_2 + a_2 b_1) \\ &= a_1 b_1 + a_2 b_2 – a_1 b_2 – a_2 b_1 \\ & = (a_2 – a_1)(b_2 – b_1) \end{align*} \]
ここで、 \( a_2 \geq a_1 \) かつ \( b_2 \geq b_1 \) であるため、 \((a_2 – a_1)(b_2 – b_1) \geq 0\) です。したがって、 \[ S_2 \geq 0 \] となり、n=2のとき成り立つことが示されました。
\( n = k \) の場合に
$$S_k=a_1 b_1 + a_2 b_2 + \cdots + a_k b_k – (a_1 b_{\sigma(1)} + a_2 b_{\sigma(2)} + \cdots + a_k b_{\sigma(k)})$$
としたとき、 \( S_k \geq 0 \) が成り立つと仮定します。
次に \( n = k + 1 \) の場合を考えます。
- \( a_1 \leq a_2 \leq \cdots \leq a_{k+1} \)
- \( b_1 \leq b_2 \leq \cdots \leq b_{k+1} \)
これらの積に関する和を考えます。
\[ S_{k+1} = \sum_{i=1}^{k+1} a_i b_i – \sum_{i=1}^{k+1} a_i b_{\sigma(i)} \]
ここで、二つのケースを考えます。
- $\sigma(k+1)=k+1$の場合
- $\sigma(k+1)\neq k+1$の場合
[1] $\sigma(k+1)=k+1$の場合、
\[ \begin{align*} S_{k+1} &= \sum_{i=1}^{k+1} a_i b_i – \sum_{i=1}^{k+1} a_i b_{\sigma(i)} \\ &=\sum_{i=1}^{k} a_i b_i+a_{k+1}b_{k+1} -\sum_{i=1}^{k} a_i b_{\sigma(i)}-a_{k+1}b_{\sigma(k+1)} \\ &=\sum_{i=1}^{k} a_i b_i-\sum_{i=1}^{k} a_i b_{\sigma(i)}+a_{k+1}b_{k+1}-a_{k+1}b_{\sigma(k+1)} \\ &=S_k+a_{k+1}b_{k+1}-a_{k+1}b_{\sigma(k+1)} \\ &\geq 0+a_{k+1}b_{k+1}-a_{k+1}b_{\sigma(k+1)} \\ &=a_{k+1}b_{k+1}-a_{k+1}b_{k+1} \\ &=0 \end{align*}\]
したがって、$\sigma(k+1)=k+1$の場合、成り立ちます。
[2] $\sigma(k+1)\neq k+1$の場合、$\sigma(k+1)=i$とすると、$a_{k+1}b_{i}$について考えます。ここで、$i$は$1\leq i\leq k$の整数とします。次に、$b_{k+1}$は$a_{j}$の積になっていると考える。言い換えると、$\sigma(j)=k+1$のときの積を考える。つまり、 $\displaystyle\sum_{i=1}^{k+1} a_i b_{\sigma(i)} $の$b_{k+1}$と$a_{k+1}$の和を取り出すと、
$$a_{k+1}b_i+a_{j}b_{k+1}$$
となる。ここで、考えたいことは$a_{k+1}\geq a_i$,$b_{k+1}\geq b_j$となるので、
$$\begin{align*} & (a_{k+1}- a_i)(b_{k+1}- b_j)\geq 0 \\ & a_{k+1}b_{k+1}+a_ib_j\geq a_{k+1}b_i+a_{j}b_{k+1} \end{align*}$$
$\sigma'(k+1)=k+1$、$\sigma'(i)=j$となる置換を考えると、
$$\begin{align*} & a_{k+1}b_{k+1}+a_ib_j\geq a_{k+1}b_i+a_{j}b_{k+1} \\ &a_{k+1}b_{\sigma'(k+1)}+a_ib_{\sigma'(i)}\geq a_{k+1}b_{\sigma(k+1)}+a_{j}b_{\sigma(j)} \\ \end{align*}$$
したがって、
$$\displaystyle\sum_{i=1}^{k+1} a_i b_{\sigma(i)} \leq \displaystyle\sum_{i=1}^{k+1} a_i b_{\sigma'(i)}$$
$S_k$について考えると、
\[ \begin{align*} S_{k+1} &= \sum_{i=1}^{k+1} a_i b_i – \sum_{i=1}^{k+1} a_i b_{\sigma(i)} \\ &\geq \sum_{i=1}^{k+1} a_i b_i – \sum_{i=1}^{k+1} a_i b_{\sigma'(i)} \end{align*}\]
置換$\sigma’$には仮定を利用することができるので、ケース[1]と同様に、示せばよいため、$S_{k+1}\geq 0$となる。
n=k+1のときも成り立つ。したがって、数学的帰納法より、$S_n\geq0$が成り立つことが示された。したがって、
$$\sum_{i=1}^n a_i b_i \geq \sum_{i=1}^n a_i b_{\sigma(i)} $$
次に、示した不等式を次の場合に対して適用すると、
- \( a_1 \leq a_2 \leq \cdots \leq a_{n} \)
- \( -b_n \leq -b_{n-1} \leq \cdots \leq -b_{1} \)
$$\sum_{i=1}^n a_i (-b_{n+1-i})\geq \sum_{i=1}^n a_i (-b_{\sigma(i)})$$
したがって、
$$\sum_{i=1}^n a_i b_{n+1-i}\leq \sum_{i=1}^n a_i b_{\sigma(i)}$$
以上のことから、
\[ \sum_{i=1}^n a_i b_i \geq \sum_{i=1}^n a_i b_{\sigma(i)} \geq \sum_{i=1}^n a_i b_{n+1-i} \]
3. 不等式の例題
を示しなさい。
対称性より、変数を \(a\geq b\geq c\geq d\geq e\) の順を考えればよい。したがって、
$$a_1=b_1=a.\quad a_2=b_2=b,\quad a_3=b_3=c,\quad a_4=b_4=d,\quad a_5=b_5=e$$
とすると、
\[ \sum_{i=1}^5 a_i^2 = a^2 + b^2 + c^2 + d^2 + e^2 \]
\[ \sum_{i=1}^5 a_i a_{i+1} = ab + bc + cd + da + ea \]
次の不等式が成り立ちます。
\[ a^2 + b^2 + c^2 + d^2 + e^2 \geq ab + bc + cd + da + ea \]
