MathLabs

第1問

実数 x1≥x2≥⋯≥xnx_1 \ge x_2 \ge \cdots \ge x_n と y1≥y2≥⋯≥yny_1 \ge y_2 \ge \cdots \ge y_n が与えられているとする。z1,z2,…,znz_1, z_2, \ldots, z_n が y1,y2,…,yny_1, y_2, \ldots, y_n の任意の並べ替えであるとき、∑i=1n(xi−yi)2≤∑i=1n(xi−zi)2\sum_{i=1}^{n} (x_i - y_i)^2 \le \sum_{i=1}^{n} (x_i - z_i)^2 が成り立つことを証明せよ。
ステップ 3/5: 鍵となる補題:順序が逆な対を入れ替えても内積は減らない
前のステップ次のステップ
ざっくり言うと

たった二つの数でも、これは問題の縮図になっている。車 AA が車 BB より大きいのにスペース AA がスペース BB より小さいなら、サイズに合わせて車を入れ替えることで駐車距離の合計は短くなることはあっても長くなることはない。

p<q, zp<zq  ⟹  xpzp+xqzq≤xpzq+xqzpp<q,\ z_p<z_q \implies x_pz_p+x_qz_q \le x_pz_q+x_qz_p
詳しい解説

ある並べ替え zz において p<qp<q かつ zp<zqz_p < z_q となる位置があるとする（xp≥xqx_p \ge x_q であるのに小さい値が大きい xx の側にある「転倒」）。zpz_p と zqz_q を入れ替えると、∑xizi\sum x_iz_i の他の項は変わらないため、xpzp+xqzqx_pz_p+x_qz_q と xpzq+xqzpx_pz_q+x_qz_p を比較すればよい。両者の差は (xpzq+xqzp)−(xpzp+xqzq)=(xp−xq)(zq−zp)≥0(x_pz_q+x_qz_p)-(x_pz_p+x_qz_q) = (x_p-x_q)(z_q-z_p) \ge 0 であり、これは xp≥xqx_p \ge x_q と 仮定より zq>zpz_q > z_p であることから従う。したがって転倒を正しい順序に直すと ∑xizi\sum x_iz_i は減少しない。