トップ› 東京大学› 1987年› 理系第5問

東京大学 1987年理系第5問解説

方針・初手

両辺の二乗を展開し、数列の各項の二乗和が順列によらず一定であることを利用して、示すべき不等式を内積の形（積の和）に簡略化する。整理した後の目標は $\sum_{j=1}^n x_j y_j \geqq \sum_{j=1}^n x_j z_j$ となる。これを証明するために、数列 $z_1, z_2, \cdots, z_n$ の中で大小関係が逆転している（すなわち $z_i < z_{i+1}$ となっている）隣り合う2項を入れ替えたとき、積の和がどのように変化するかを評価する。

解法1

示すべき不等式の両辺を展開すると、

$$ \sum_{j=1}^{n} (x_j^2 - 2x_j y_j + y_j^2) \leqq \sum_{j=1}^{n} (x_j^2 - 2x_j z_j + z_j^2) $$

ここで、$z_1, z_2, \cdots, z_n$ は $y_1, y_2, \cdots, y_n$ を並べかえた数列であるから、含まれる項の集合は重複度を含めて一致する。したがって、各項の二乗和は等しくなり、

$$ \sum_{j=1}^{n} y_j^2 = \sum_{j=1}^{n} z_j^2 $$

が成り立つ。両辺から共通する $\sum_{j=1}^{n} x_j^2$ と上記の二乗和を引いて整理すると、

$$ -2 \sum_{j=1}^{n} x_j y_j \leqq -2 \sum_{j=1}^{n} x_j z_j $$

両辺を $-2$ で割り、不等号の向きを反転させると、

$$ \sum_{j=1}^{n} x_j y_j \geqq \sum_{j=1}^{n} x_j z_j $$

を得る。よって、この不等式が成り立つことを示せばよい。

数列 $z_1, z_2, \cdots, z_n$ が $y_1, y_2, \cdots, y_n$ と完全に一致していないとする。$y_1 \geqq y_2 \geqq \cdots \geqq y_n$ であるから、$z_1, z_2, \cdots, z_n$ は全体として降順には並んでいない。したがって、隣り合う2項で $z_i < z_{i+1}$ を満たす整数 $i$ （$1 \leqq i \leqq n-1$）が少なくとも1つ存在する。

この $z_i$ と $z_{i+1}$ を入れ替えた新しい数列を $z'_1, z'_2, \cdots, z'_n$ とする。すなわち、

$$ z'_j = \begin{cases} z_{i+1} & (j = i) \\ z_i & (j = i+1) \\ z_j & (j \neq i, i+1) \end{cases} $$

とする。このとき、入れ替え前後での積の和の差を計算すると、

$$ \sum_{j=1}^{n} x_j z'_j - \sum_{j=1}^{n} x_j z_j = (x_i z'_i + x_{i+1} z'_{i+1}) - (x_i z_i + x_{i+1} z_{i+1}) $$

$$ = x_i z_{i+1} + x_{i+1} z_i - x_i z_i - x_{i+1} z_{i+1} $$

$$ = x_i (z_{i+1} - z_i) - x_{i+1} (z_{i+1} - z_i) $$

$$ = (x_i - x_{i+1})(z_{i+1} - z_i) $$

問題の条件より $x_1 \geqq x_2 \geqq \cdots \geqq x_n$ であるから $x_i - x_{i+1} \geqq 0$ である。また、選び方から $z_{i+1} - z_i > 0$ である。したがって、

$$ (x_i - x_{i+1})(z_{i+1} - z_i) \geqq 0 $$

となり、

$$ \sum_{j=1}^{n} x_j z'_j \geqq \sum_{j=1}^{n} x_j z_j $$

が成り立つ。これは、隣り合う昇順のペアを降順に入れ替える操作を行うと、積の和 $\sum_{j=1}^{n} x_j z_j$ の値は減少しない（増加するか、または変わらない）ことを意味する。

どのような並べかえ $z_1, z_2, \cdots, z_n$ であっても、この「隣り合う昇順のペアを降順に入れ替える」という操作を繰り返せば、有限回の操作で逆転しているペアがなくなり、すべての項が降順に並んだ数列、すなわち $y_1, y_2, \cdots, y_n$ に到達する。

この有限回の操作の過程で、積の和 $\sum_{j=1}^{n} x_j z_j$ の値は一度も減少することはないため、最終的に得られる和 $\sum_{j=1}^{n} x_j y_j$ は元の和以上である。よって、

$$ \sum_{j=1}^{n} x_j y_j \geqq \sum_{j=1}^{n} x_j z_j $$

が示された。これより、元の不等式も成り立つ。

解説

不等式の証明における有名事実「再配列不等式（Rearrangement Inequality）」の基本定理を証明する問題である。二つの数列がどちらも同じ順序（この場合は降順）で並んでいるとき、同じ位置にある項同士の積の和が最大になるという直感的な事実を厳密に証明させている。差の計算によって積の和の比較に帰着させることが第一のステップである。第二のステップである最大性の証明においては、数列の「隣接互換」を利用する。大小関係が逆転している部分に注目し、それを解消するように入れ替えを行ったときに値が単調に非減少となることを示し、最終的な目的の並びに到達させる論法は、順列や配置の極値問題において非常に強力な定石である。