MathLabs

Problem 1

Let x1≥x2≥⋯≥xnx_1 \ge x_2 \ge \cdots \ge x_n and y1≥y2≥⋯≥yny_1 \ge y_2 \ge \cdots \ge y_n be real numbers. Prove that if z1,z2,…,znz_1, z_2, \ldots, z_n is any permutation of y1,y2,…,yny_1, y_2, \ldots, y_n, then ∑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.
Step 5 of 5: Conclude the original inequality
Previous stepNext step
∑i=1nxiyi≥∑i=1nxizi  ⟹  ∑i=1n(xi−yi)2≤∑i=1n(xi−zi)2\sum_{i=1}^n x_iy_i \ge \sum_{i=1}^n x_iz_i \implies \sum_{i=1}^n (x_i-y_i)^2 \le \sum_{i=1}^n (x_i-z_i)^2
Detailed analysis

Step 3 shows ∑xiyi≥∑xizi\sum x_iy_i \ge \sum x_iz_i for the arbitrary permutation zz we started with, which by Step 1 is exactly equivalent to ∑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. Since zz was an arbitrary permutation of yy, the inequality holds for every permutation, completing the proof. Equality holds throughout exactly when every inversion-fixing swap changed nothing, i.e. when zz already pairs equal values the same way as yy does.