問題
を2以上の自然数とする．およびを満足する数列およびが与えられている．を並べかえて得られるどのような数列に対しても
が成り立つことを証明せよ．
出典：東京大学 1987年度 前期日程 第2次学力試験 理系 第5問
方針
並べ替えられた に、順序が逆になっている2項 、 があるとき、その2項を交換する。 を使うと、交換後の二乗和は交換前以下になる。したがって順序の入れ替わりを1つずつ直していけば和は増えず、最後に は降順、すなわち与えられた の並びになる。別の見方として、二乗和のうち並べ替えで変わるのは だけである。
解答
任意の並べ替え を考える。もしある について となっていれば、この2項の順序は とは逆になっている。この2項だけを交換したとき、二乗和の変化を調べる。
交換前の該当部分は であり、交換後は である。差を計算すると
ここで 、 だから である。したがって、この交換を行うと二乗和は増えない。
この操作を、 の中で順序が逆になっている2項がなくなるまで繰り返す。各交換で二乗和は増えず、最終的には となる。ところが は の並べ替えであり、もともと だから、最終的な並びは である。
よって任意の並べ替え に対して が成り立つ。
別解。展開すると
である。 は の並べ替えなので、前半2つの和は並べ替えによらない。したがって二乗和を最小にすることは を最大にすることと同じであり、上の交換計算は、降順同士を対応させるとこの和が最大になることを示している。