Evolton

東京大学 1987年度 前期日程 第2次学力試験理系数学 第5問

nを2以上の自然数とする.
x1≧x2≧⋯≧xnおよびy1≧y2≧⋯≧yn
を満足する数列x1,x2,⋯ ,xnおよびy1,y2,⋯ ,ynが与えられている.
y1,y2,⋯ ,ynを並べかえて得られるどのような数列z1,z2,⋯ ,znに対しても∑j=1n(xj−yj)2≦∑j=1n(xj−zj)2が成り立つことを証明せよ.

難易度6/ 10計算量5/ 10目安16分

数列、論証・証明 不等式評価、対称性の利用

方針

並べ替えられた z に、順序が逆になっている2項 i<j、zi<zj があるとき、その2項を交換する。xi≧xj を使うと、交換後の二乗和は交換前以下になる。したがって順序の入れ替わりを1つずつ直していけば和は増えず、最後に z は降順、すなわち与えられた y の並びになる。

解答

任意の並べ替え z1,z2,…,zn を考える。もしある i<j について zi<zj となっていれば、この2項の順序は xi≧xj とは逆になっている。この2項だけを交換したとき、二乗和の変化を調べる。

交換前の該当部分は (xi−zi)2+(xj−zj)2 であり、交換後は (xi−zj)2+(xj−zi)2 である。差を計算すると{(xi−zi)2+(xj−zj)2}−{(xi−zj)2+(xj−zi)2}=2(xi−xj)(zj−zi).ここで xi≧xj、zj>zi だから 2(xi−xj)(zj−zi)≧0 である。したがって、この交換を行うと二乗和は増えない。

この操作を、z の中で順序が逆になっている2項がなくなるまで繰り返す。各交換で二乗和は増えず、最終的には z1≧z2≧⋯≧zn となる。ところが z1,…,zn は y1,…,yn の並べ替えであり、もともと y1≧y2≧⋯≧yn だから、最終的な並びは y1,y2,…,yn である。

よって任意の並べ替え z に対して ∑j=1n(xj−yj)2≦∑j=1n(xj−zj)2 が成り立つ。

別解

解法2:最大の項を固定して帰納法で示す

方針

二乗和を最小にする並べ方を一つ取る。最大の x1 に最大の y1 が対応していなければ、その二つの対応先を交換して和が増えないことを示す。x1,y1 を固定した後、残る n−1 項に同じ議論を適用する。

解答

n に関する帰納法で示す。n=2 のときは(x1−y2)2+(x2−y1)2−{(x1−y1)2+(x2−y2)2}=2(x1−x2)(y1−y2)≧0だから成り立つ。

n−1 項まで成り立つと仮定する。任意の並べ替え z1,…,zn の中で、y1 が k 番目にあるとする。z1 と zk=y1 を交換したとき、交換前から交換後を引くと2(x1−xk)(y1−z1)≧0である。したがって、y1 を x1 に対応させても二乗和は増えない。

残る x2,…,xn と y2,…,yn はいずれも降順である。帰納法の仮定により、この残りも同じ順に対応させたとき二乗和が最小になる。よって全体でも∑j=1n(xj−yj)2≦∑j=1n(xj−zj)2が成り立つ。

総評

難度6、計算量5、目安時間16分。交換法では逆順の2項を直したとき二乗和が増えないことと、有限回で降順に到達することを書く。帰納法では最大項同士を対応させても悪化しないことを示し、残る項へ帰納法を適用する。原問題に行列はなく、二つの証明はいずれも展開と順序だけで完結する。

Evolton Pro

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

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

出典: 東京大学 1987年度 第2次学力試験 数学。問題文はHTML表示のために再入力・数式組版しています。