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 2 of 5: Expand the squares to isolate the cross term
Previous stepNext step
∑i=1n(xi−yi)2≤∑i=1n(xi−zi)2  ⟺  ∑i=1nxiyi≥∑i=1nxizi\sum_{i=1}^n (x_i-y_i)^2 \le \sum_{i=1}^n (x_i-z_i)^2 \iff \sum_{i=1}^n x_i y_i \ge \sum_{i=1}^n x_i z_i
Detailed analysis

Expanding both sides gives ∑xi2−2∑xiyi+∑yi2\sum x_i^2 - 2\sum x_i y_i + \sum y_i^2 and ∑xi2−2∑xizi+∑zi2\sum x_i^2 - 2\sum x_i z_i + \sum z_i^2. Since zz is only a reordering of yy, ∑yi2=∑zi2\sum y_i^2 = \sum z_i^2 and ∑xi2\sum x_i^2 is common to both sides, so after cancelling identical terms the original inequality is exactly equivalent to ∑xiyi≥∑xizi\sum x_i y_i \ge \sum x_i z_i: the sorted pairing of xx with yy gives the largest possible dot product among all pairings of xx with a permutation of yy.