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)}
详细分析

取 yy 的任意一个尚未按 y1≥⋯≥yny_1 \ge \cdots \ge y_n 排好序的排列 zz。那么其中必存在至少一个逆序对 p<qp<q 满足 zp<zqz_p<z_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。