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（一个“逆序”:较小的值恰好配上了较大的 xx,因为 xp≥xqx_p \ge x_q）。交换 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 减小。