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 4 of 5: Sort any permutation into the fully ordered one by repeated swaps
Previous stepNext step
∑ixiyi=max⁡σ∑ixi yσ(i)\sum_i x_iy_i=\max_{\sigma}\sum_i x_i\,y_{\sigma(i)}
Detailed analysis

Take any permutation zz of yy that is not already sorted as y1≥⋯≥yny_1 \ge \cdots \ge y_n. Then it must contain at least one inversion p<qp<q with zp<zqz_p<z_q; by the lemma, swapping them gives a new permutation with ∑xizi\sum x_iz_i no smaller, and strictly fewer inversions (an elementary counting fact about adjacent-style swaps on a finite sequence). Repeating this finitely many times eliminates every inversion, since the number of inversions is a nonnegative integer that strictly decreases at each step, and the process must terminate at the fully sorted sequence y1≥⋯≥yny_1 \ge \cdots \ge y_n itself. Along the way ∑xizi\sum x_iz_i never decreased, so its final value ∑xiyi\sum x_iy_i is at least as large as the value ∑xizi\sum x_iz_i we started with.