Problem 1

Let

x_1 \ge x_2 \ge \cdots \ge x_n

and

y_1 \ge y_2 \ge \cdots \ge y_n

be real numbers. Prove that if

z_1, z_2, \ldots, z_n

is any permutation of

y_1, y_2, \ldots, y_n

, then

\sum_{i=1}^{n} (x_i - y_i)^2 \le \sum_{i=1}^{n} (x_i - z_i)^2

Step 3 of 5: Key lemma: swapping an out-of-order pair never decreases the dot product

Previous step Next step

In plain words

With just two numbers this is the whole problem in miniature: if car $A$ is bigger than car $B$ but spot $A$ is smaller than spot $B$ , swapping the cars to match sizes can only shorten the total parking distance, never lengthen it.

p<q,\ z_p<z_q \implies x_pz_p+x_qz_q \le x_pz_q+x_qz_p

Detailed analysis

Suppose in some permutation $z$ there are positions $p<q$ with $z_p < z_q$ (an "inversion": a smaller value sits where a larger $x$ is, since $x_p \ge x_q$ ). Swap $z_p$ and $z_q$ ; every other term of $\sum x_iz_i$ is unchanged, so it suffices to compare $x_pz_p+x_qz_q$ with $x_pz_q+x_qz_p$ . Their difference is $(x_pz_q+x_qz_p)-(x_pz_p+x_qz_q) = (x_p-x_q)(z_q-z_p) \ge 0$ , because $x_p \ge x_q$ and $z_q > z_p$ by assumption. Hence swapping the inversion into the correct order weakly increases $\sum x_iz_i$ .