東京大学 2007年度後期・理系数学後期第3問解答・解説

問題

$N ≧ 2$ を自然数とし、 $x_{1} ≦ \dots ≦ x_{N}$ を満たす実数列に対して、 $k_{n}, p_{n}, q_{n}$ を次で定める。初めに $k_{0} = 1, p_{0} = x_{1}, q_{0} = x_{N}$ とする。 $n$ が奇数のとき、 $k_{n}$ を $x_{i} ≦ (p_{n - 1} + q_{n - 1}) /2$ を満たす $x_{i}$ の個数とし、 $p_{n} = p_{n - 1}, q_{n} = q_{n - 1}$ とする。 $n ≧ 2$ が偶数のとき、 $k_{n} = k_{n - 1}$ とし

p_{n} = \frac{1}{k _{n}} i = 1 \sum k_{n} x_{i}, q_{n} = \frac{1}{N - k _{n}} i = k_{n} + 1 \sum N x_{i}

とする。ただし $k_{n} = 0$ または $N$ となれば手続きを終了する。 $x_{1} < x_{N}$ とする。

(1) 全ての自然数 $n$ について $1 ≦ k_{n} ≦ N - 1$ かつ $x_{1} ≦ p_{n} < q_{n} ≦ x_{N}$ を示せ。

(2)

J_{n} = i = 1 \sum k_{n} (x_{i} - p_{n})^{2} + i = k_{n} + 1 \sum N (x_{i} - q_{n})^{2}

とすると、全ての自然数 $n$ に対して $J_{n} ≦ J_{n - 1}$ を示せ。

(3) $n$ が十分大きいとき、 $J_{n} = J_{n - 1}$ 、 $p_{n} = p_{n - 1}$ 、 $q_{n} = q_{n - 1}$ 、 $k_{n} = k_{n - 1}$ が成り立つことを示せ。

出典：東京大学 2007年度後期日程第2次学力試験後期・理系後期第3問

方針

(1)は奇数段階の中点分割と、偶数段階の各群の平均について帰納的に示す。(2)は奇数段階では各 $x_{i}$ を近い中心へ割り当てる操作、偶数段階では固定した群に対する平方和を平均値で最小化する操作と見る。(3)は偶数段階の状態が分割位置 $k$ だけで決まり、その候補が有限個しかないことを使う。

解答

(1)

$n = 0$ では仮定から

1 ≦ k_{0} = 1 ≦ N - 1, x_{1} = p_{0} < q_{0} = x_{N}

である。以下、1つ前の段階で主張が成り立つとする。

$n$ が奇数のとき、 $m = (p_{n - 1} + q_{n - 1}) /2$ とおく。 $p_{n - 1} < q_{n - 1}$ より

x_{1} ≦ p_{n - 1} < m < q_{n - 1} ≦ x_{N} .

したがって $x_{i} ≦ m$ を満たすものも、満たさないものも少なくとも1個あり

1 ≦ k_{n} ≦ N - 1

である。 $p_{n}, q_{n}$ は変化しないので、残りの不等式も保たれる。

$n$ が偶数のとき、 $1 ≦ k_{n} ≦ N - 1$ はそのままである。平均値の性質と大小順から

x_{1} ≦ p_{n} ≦ x_{k_{n}} ≦ x_{k_{n} + 1} ≦ q_{n} ≦ x_{N} .

もし $p_{n} = q_{n}$ なら、この不等式は全て等号となり $x_{1} = x_{N}$ になってしまう。よって $p_{n} < q_{n}$ である。以上から帰納的に主張が成り立ち、手続きは途中で終了しない。

(2)

まず $n$ が奇数とする。 $p_{n} = p_{n - 1} = p, q_{n} = q_{n - 1} = q$ で $p < q$ である。このとき

(x - p)^{2} ≦ (x - q)^{2} ⟺ x ≦ \frac{p + q}{2} .

したがって新しい $k_{n}$ は、各 $x_{i}$ を $p, q$ のうち距離の近い方へ割り当てた結果である。各項ごとに二乗距離は増えないので $J_{n} ≦ J_{n - 1}$ である。

次に $n$ が偶数とする。実数 $z_{1}, \dots, z_{h}$ の平均を $\overset{z}{ˉ}$ とすれば、任意の実数 $c$ に対して

i = 1 \sum h (z_{i} - c)^{2} = i = 1 \sum h (z_{i} - \overset{z}{ˉ})^{2} + h (c - \overset{z}{ˉ})^{2}

である。したがって二乗偏差の和は $c = \overset{z}{ˉ}$ のとき最小となる。偶数段階では分割位置 $k_{n} = k_{n - 1}$ を変えず、前半と後半の中心をそれぞれの平均 $p_{n}, q_{n}$ に更新するので、やはり $J_{n} ≦ J_{n - 1}$ である。

(3)

$n ≧ 2$ が偶数のとき、 $p_{n}, q_{n}$ は $k_{n}$ によって

p_{n} = \frac{1}{k _{n}} i = 1 \sum k_{n} x_{i}, q_{n} = \frac{1}{N - k _{n}} i = k_{n} + 1 \sum N x_{i}

と一意に定まる。 $k_{n}$ の候補は $1, 2, \dots, N - 1$ の有限個だから、偶数段階の状態 $(k_{n}, p_{n}, q_{n}, J_{n})$ も有限個しかない。

さらに、ある偶数段階から次の偶数段階までに分割位置が変われば、(2)の2回の不等式の少なくとも一方は厳密になる。実際、奇数段階で距離が厳密に小さい群へ移る点があれば、その段階で $J$ は減る。等距離の点だけが後半から前半へ移る場合でも、その値は $(p + q) /2$ であって $p$ とは異なるため、次の偶数段階で前半の平均を取り直すと二乗偏差の和が厳密に減る。したがって状態が変わる限り、偶数番目の $J_{n}$ は厳密に減少する。

有限個の状態の間を厳密に減少し続けることはできない。よって十分大きい偶数 $n$ からは分割位置が変わらず、平均も変わらない。その間の奇数段階でも中点による再分類は同じ分割を返す。したがって十分大きい全ての $n$ について

J_{n} = J_{n - 1}, p_{n} = p_{n - 1}, q_{n} = q_{n - 1}, k_{n} = k_{n - 1}

が成り立つ。

東京大学 2007年度後期・理系数学 後期 第3問

問題

方針

解答

(1)

(2)

(3)

東京大学 2007年度
後期・理系数学後期第3問