IMO 1975 SL 2

Origin: CZS

Problem

Let x1 \geqx2 \geq\cdot \cdot \cdot \geqxn and y1 \geqy2 \geq\cdot \cdot \cdot \geqyn be two n-tuples of numbers. Prove that n  i=1 (xi −yi)2 \leq n  i=1 (xi −zi)2 is true when z1, z2, . . . , zn denote y1, y2, . . . , yn taken in another order.

Solution

Since there are finitely many arrangements of the zi’s, assume that z1, . . . , zn is the one for which n i=1(xi −zi)2 is minimal. We claim that in this case i < j ⇒zi \geqzj, from which the claim of the problem directly follows. Indeed, otherwise we would have (xi −zj)2 + (xj −zi)2 = (xi −zi)2 + (xj −zj)2 +2(xizi + xjzj −xizj −xjzi) = (xi −zi)2 + (xj −zj)2 + 2(xi −xj)(zi −zj) \leq(xi −zi)2 + (xj −zj)2, contradicting the assumption.