東京大学 2007年度 後期日程 第2次学力試験理系（後期）数学 第3問

(1) $n=0$ では仮定から$$1\leqq k_0=1\leqq N-1,x_1=p_0<q_0=x_N$$である。以下、1つ前の段階で主張が成り立つとする。

$n$ が奇数のとき、$m=(p_{n-1}+q_{n-1})\mathrm{/}2$ とおく。$p_{n-1}<q_{n-1}$ より$$x_1\leqq p_{n-1}<m<q_{n-1}\leqq x_N\mathrm{.}$$したがって $x_i\leqq m$ を満たすものも、満たさないものも少なくとも1個あり$$1\leqq k_n\leqq N-1$$である。$p_n,q_n$ は変化しないので、残りの不等式も保たれる。

$n$ が偶数のとき、$1\leqq k_n\leqq N-1$ はそのままである。平均値の性質と大小順から$$x_1\leqq p_n\leqq x_{k_n}\leqq x_{k_n+1}\leqq q_n\leqq x_N\mathrm{.}$$もし $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\leqq (x-q{)}^2⟺x\leqq {\displaystyle \frac{p+q}{2}}\mathrm{.}$$したがって新しい $k_n$ は、各 $x_i$ を $p,q$ のうち距離の近い方へ割り当てた結果である。各項ごとに二乗距離は増えないので $J_n\leqq J_{n-1}$ である。

次に $n$ が偶数とする。実数 $z_1,\dots ,z_h$ の平均を $\bar{z}$ とすれば、任意の実数 $c$ に対して$$\sum _{i=1}^h(z_i-c{)}^2=\sum _{i=1}^h(z_i-\bar{z}{)}^2+h(c-\bar{z}{)}^2$$である。したがって二乗偏差の和は $c=\bar{z}$ のとき最小となる。偶数段階では分割位置 $k_n=k_{n-1}$ を変えず、前半と後半の中心をそれぞれの平均 $p_n,q_n$ に更新するので、やはり $J_n\leqq J_{n-1}$ である。

(3) $n\geqq 2$ が偶数のとき、$p_n,q_n$ は $k_n$ によって$$p_n={\displaystyle \frac{1}{k_n}}\sum _{i=1}^{k_n}{x}_i,q_n={\displaystyle \frac{1}{N-k_n}}\sum _{i=k_n+1}^N{x}_i$$と一意に定まる。$k_n$ の候補は $1,2,\dots ,N-1$ の有限個だから、偶数段階の状態 $(k_n,p_n,q_n,J_n)$ も有限個しかない。

さらに、ある偶数段階から次の偶数段階までに分割位置が変われば、(2)の2回の不等式の少なくとも一方は厳密になる。実際、奇数段階で距離が厳密に小さい群へ移る点があれば、その段階で $J$ は減る。等距離の点だけが後半から前半へ移る場合でも、その値は $(p+q)\mathrm{/}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}$$が成り立つ。

奇数段階は中点で再分類し、偶数段階は各群の平均へ中心を更新する。