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 が成り立つことを証明せよ。
ステップ 4/5: 繰り返し入れ替えることで任意の並べ替えを完全に整列させる
前のステップ次のステップ
∑ixiyi=max⁡σ∑ixi yσ(i)\sum_i x_iy_i=\max_{\sigma}\sum_i x_i\,y_{\sigma(i)}
詳しい解説

y1≥⋯≥yny_1 \ge \cdots \ge y_n の順にまだ整列していない yy の任意の並べ替え zz を考える。このとき zp<zqz_p<z_q となる転倒 p<qp<q が少なくとも一つ存在する。上の補題により、それらを入れ替えると ∑xizi\sum x_iz_i が減らない新しい並べ替えが得られ、しかも転倒の個数は真に減少する（有限数列上の入れ替えに関する初等的な計数事実）。これを有限回繰り返せばすべての転倒が解消される。なぜなら転倒の個数は各ステップで真に減少する非負整数であり、この過程は完全に整列した数列 y1≥⋯≥yny_1 \ge \cdots \ge y_n 自身で終わらざるを得ないからである。この過程の間、∑xizi\sum x_iz_i は一度も減少しなかったので、最終的な値 ∑xiyi\sum x_iy_i は出発点の値 ∑xizi\sum x_iz_i 以上である。