Evolton

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

Nを2以上の自然数とする.
x1≦⋯≦xNをみたす実数x1,⋯ ,xNに対し,
実数kn,pn,qn (n=0,1,2,⋯ )を次の手続きで定める.

(A) k0=1,p0=x1,q0=xN

(B) nが奇数のときknはxi≦pn−1+qn−12をみたすxiの個数,
pn=pn−1,qn=qn−1

(C) nが偶数(n≧2)のときkn=kn−1,pn=1kn∑i=1knxi,qn=1N−kn∑i=kn+1Nxiただしkn=0またはkn=Nとなったら,その時点で手続きを終了する.

x1<xNであるとき,次の問に答えよ.

(1) すべての自然数nについて1≦kn≦N−1かつx1≦pn<qn≦xNが成り立つことを示せ.

(2) 実数Jn (n=0,1,2,⋯ )をJn=∑i=1kn(xi−pn)2+∑i=kn+1N(xi−qn)2と定めると,
すべての自然数nに対してJn≦Jn−1が成り立つことを示せ.

(3) nが十分大きいとき.
Jn=Jn−1,pn=pn−1,qn=qn−1,kn=kn−1が成り立つことを示せ.

難易度9/ 10計算量7/ 10目安40分

数列、方程式・不等式、論証・証明 状態分類、不等式評価、式変形、一意性証明、発想重視

方針

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

解答

(1) n=0 では仮定から1≦k0=1≦N−1,x1=p0<q0=xNである。以下、1つ前の段階で主張が成り立つとする。

n が奇数のとき、m=(pn−1+qn−1)/2 とおく。pn−1<qn−1 よりx1≦pn−1<m<qn−1≦xN.したがって xi≦m を満たすものも、満たさないものも少なくとも1個あり1≦kn≦N−1である。pn,qn は変化しないので、残りの不等式も保たれる。

n が偶数のとき、1≦kn≦N−1 はそのままである。平均値の性質と大小順からx1≦pn≦xkn≦xkn+1≦qn≦xN.もし pn=qn なら、この不等式は全て等号となり x1=xN になってしまう。よって pn<qn である。以上から帰納的に主張が成り立ち、手続きは途中で終了しない。

(2) まず n が奇数とする。pn=pn−1=p, qn=qn−1=q で p<q である。このとき(x−p)2≦(x−q)2⟺x≦p+q2.したがって新しい kn は、各 xi を p,q のうち距離の近い方へ割り当てた結果である。各項ごとに二乗距離は増えないので Jn≦Jn−1 である。

次に n が偶数とする。実数 z1,…,zh の平均を zˉ とすれば、任意の実数 c に対して∑i=1h(zi−c)2=∑i=1h(zi−zˉ)2+h(c−zˉ)2である。したがって二乗偏差の和は c=zˉ のとき最小となる。偶数段階では分割位置 kn=kn−1 を変えず、前半と後半の中心をそれぞれの平均 pn,qn に更新するので、やはり Jn≦Jn−1 である。

(3) n≧2 が偶数のとき、pn,qn は kn によってpn=1kn∑i=1knxi,qn=1N−kn∑i=kn+1Nxiと一意に定まる。kn の候補は 1,2,…,N−1 の有限個だから、偶数段階の状態 (kn,pn,qn,Jn) も有限個しかない。

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

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

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

総評

難度9、計算量7。想定時間は40分程度。この手続きは「近い中心への再分類」と「各群の平均への中心更新」を交互に行う。前者は各点ごと、後者は平方完成で評価すると Jn の単調性が見える。収束だけでなく有限回で停止する理由は、偶数段階の状態が N−1 個の分割候補に限られることにある。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る東大の数列の問題で問題集を作る

出典: 東京大学 2007年度 後期 理科 数学。問題文はHTML表示のために再入力・数式組版しています。