トップ› 大阪大学› 1968年› 文系第1問

大阪大学 1968年文系第1問解説

方針・初手

与えられた和は、足し算の順序を入れ替えても値が変わらないため、数列 $\{a_n\}$ を小さい順（昇順）に固定して考えても一般性を失いません。このとき、数列 $\{b_n\}$ の要素の並び順によって和がどのように変化するかを、2つの項の入れ替えによる差分を計算することで調べます。これにより、和が最大・最小となる配置を論理的に特定し、その後の計算に帰着させます。

解法1

$n$ 個の奇数 $1, 3, \cdots, 2n-1$ を小さい順に並べたものを $x_1, x_2, \cdots, x_n$ とすると、$x_k = 2k-1$ である。同様に、$n$ 個の偶数 $2, 4, \cdots, 2n$ を小さい順に並べたものを $y_1, y_2, \cdots, y_n$ とすると、$y_k = 2k$ である。

与えられた和を $S$ とする。

$$ S = a_1b_1 + a_2b_2 + \cdots + a_nb_n = \sum_{k=1}^n a_k b_k $$

足し算の順序を入れ替えても和 $S$ は変わらないため、一般性を失わず、$a_1 < a_2 < \cdots < a_n$ と固定してよい。すなわち、$a_k = 2k-1$ とする。このとき、$b_1, b_2, \cdots, b_n$ は偶数 $y_1, y_2, \cdots, y_n$ のある並べ替えとなる。

(i) 最大値について

数列 $\{b_n\}$ の中に、$i < j$ かつ $b_i > b_j$ を満たす組 $(i, j)$ が存在すると仮定する。このとき、$b_i$ と $b_j$ の位置を入れ替えた新しい和を $S'$ とすると、入れ替えに関与しない項は相殺されるため、次が成り立つ。

$$ S' - S = (a_i b_j + a_j b_i) - (a_i b_i + a_j b_j) = (a_j - a_i)(b_i - b_j) $$

$i < j$ より $a_i < a_j$ であるから $a_j - a_i > 0$ であり、仮定より $b_i - b_j > 0$ であるから、

$$ S' - S > 0 $$

となり、逆転している大小関係を揃えるように要素を入れ替えることで、和 $S$ は必ず大きくなる。この操作を繰り返すことで和は単調に増加し、最終的にすべての組で $b_i < b_j$ が成り立つとき、つまり $b_1 < b_2 < \cdots < b_n$ となるときに和 $S$ は最大となる。すなわち、$b_k = y_k = 2k$ のとき最大値をとる。

最大値を $M$ とすると、

$$ M = \sum_{k=1}^n (2k-1)(2k) = \sum_{k=1}^n (4k^2 - 2k) $$

$$ M = 4 \cdot \frac{1}{6}n(n+1)(2n+1) - 2 \cdot \frac{1}{2}n(n+1) $$

$$ M = \frac{2}{3}n(n+1)(2n+1) - n(n+1) = n(n+1) \left( \frac{4n+2}{3} - 1 \right) $$

$$ M = \frac{1}{3}n(n+1)(4n-1) $$

(ii) 最小値について

同様に、数列 $\{b_n\}$ の中に、$i < j$ かつ $b_i < b_j$ を満たす組 $(i, j)$ が存在すると仮定する。 $b_i$ と $b_j$ の位置を入れ替えた新しい和を $S''$ とすると、

$$ S'' - S = (a_i b_j + a_j b_i) - (a_i b_i + a_j b_j) = (a_j - a_i)(b_i - b_j) $$

$a_j - a_i > 0$ であり、仮定より $b_i - b_j < 0$ であるから、

$$ S'' - S < 0 $$

となり、同じ大小関係を持つ要素を入れ替えて逆転させることで、和 $S$ は必ず小さくなる。この操作を繰り返すことで和は単調に減少し、最終的にすべての組で $b_i > b_j$ が成り立つとき、つまり $b_1 > b_2 > \cdots > b_n$ となるときに和 $S$ は最小となる。すなわち、$b_k = y_{n-k+1} = 2(n-k+1)$ のとき最小値をとる。

最小値を $m$ とすると、

$$ m = \sum_{k=1}^n (2k-1)\{2(n-k+1)\} $$

ここで、$2(n-k+1) = (2n+1) - (2k-1)$ と変形できることを利用すると、計算が簡明になる。

$$ m = \sum_{k=1}^n (2k-1)\{(2n+1) - (2k-1)\} = (2n+1)\sum_{k=1}^n (2k-1) - \sum_{k=1}^n (2k-1)^2 $$

奇数の和は $\sum_{k=1}^n (2k-1) = n^2$ であり、奇数の平方の和は次のように計算できる。

$$ \sum_{k=1}^n (2k-1)^2 = \sum_{k=1}^n (4k^2 - 4k + 1) $$

$$ = 4 \cdot \frac{1}{6}n(n+1)(2n+1) - 4 \cdot \frac{1}{2}n(n+1) + n $$

$$ = \frac{2}{3}n(n+1)(2n+1) - 2n(n+1) + n $$

$$ = \frac{n}{3} \{ 2(n+1)(2n+1) - 6(n+1) + 3 \} $$

$$ = \frac{n}{3} (4n^2 + 6n + 2 - 6n - 6 + 3) = \frac{n(4n^2-1)}{3} $$

これらを代入して、最小値 $m$ を求める。

$$ m = (2n+1)n^2 - \frac{n(4n^2-1)}{3} $$

$$ m = \frac{3n^2(2n+1) - n(2n-1)(2n+1)}{3} $$

$$ m = \frac{n(2n+1)\{3n - (2n-1)\}}{3} $$

$$ m = \frac{1}{3}n(n+1)(2n+1) $$

解説

2つの数列の要素を1対1で掛け合わせて和をとるとき、「大きいもの同士、小さいもの同士を掛け合わせたとき」に和が最大となり、「大きいものと小さいものを掛け合わせたとき」に和が最小となるという性質を利用する問題です。この性質は「並べ替えの不等式」として知られています。直感的に明らかに見える性質ですが、解答においては自明とせず、本解のように「2つの要素の交換による差分」を計算して単調性を証明する論証が求められます。最小値のシグマ計算においては、項の対称性を利用して式を上手く括ることで計算量を減らす工夫が有効です。