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 1 of 5: What the inequality says
Previous stepNext step
In plain words

Think of xix_i as nn fixed parking spots on a number line and yiy_i as nn cars that must park in some order. Pairing the biggest car with the biggest spot, the second biggest with the second biggest, and so on (the "sorted" pairing yiy_i) keeps every car as close as possible to its spot on average. Shuffling the cars into any other order ziz_i can only make the total squared parking distance larger, never smaller. This problem asks for a rigorous proof of that intuition.

∑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
Detailed analysis

Both sides of the inequality are sums of nn squared differences between the fixed sequence xix_i and a sequence built from the same multiset {y1,…,yn}\{y_1, \ldots, y_n\}: on the left the sequence is already sorted the same way as xx, on the right it is an arbitrary rearrangement zz. The claim is that the sorted pairing minimizes the sum of squared differences among all n!n! possible pairings.