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 が成り立つことを証明せよ。
ステップ 1/5: この不等式が何を主張しているか
前のステップ次のステップ
ざっくり言うと

xix_i を数直線上に固定された nn 個の駐車スペース、yiy_i をある順序で停めなければならない nn 台の車だと考えてみよう。一番大きい車を一番大きいスペースに、二番目に大きい車を二番目に大きいスペースに、というように対応させる「整列させた」組み合わせ yiy_i が、各車をスペースにできるだけ近づける。車を別の順序 ziz_i に入れ替えると、駐車距離の二乗の合計は大きくなることはあっても小さくなることはない。この問題はその直感を厳密に証明せよというものである。

∑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
詳しい解説

不等式の両辺は、固定された数列 xix_i と同じ多重集合 {y1,…,yn}\{y_1, \ldots, y_n\} から作られる数列との差の二乗の和である。左辺ではその数列はすでに xx と同じ順序に整列しており、右辺は任意の並べ替え zz である。主張は、整列させた組み合わせが nn 個の項の二乗和を比較する n!n! 通りの組み合わせの中で差の二乗の和を最小にするということである。