IMO 1975 Problem 1
The expression to be minimized is
Proposed by: -
Verified: yes
Verdicts: PASS + PASS
Solve time: 5m39s
Problem
Let $x_i, y_i~(i = 1, 2, \ldots, n)$ be real numbers such that $$ x_1 \geq x_2 \geq \cdots \geq x_n \text{ and } y_1 \geq y_2 \geq \cdots \geq y_n. $$ Prove that, if $z_1, z_2, \cdots, z_n$ is any permutation of $y_1, y_2, \cdots, y_n$, then $$ \sum_{i=1}^n (x_i - y_i)^2 \leq \sum_{i=1}^n (x_i - z_i)^2. $$
Exploration
The expression to be minimized is
$$\sum_{i=1}^{n}(x_i-z_i)^2,$$
where $(z_1,\dots,z_n)$ is a permutation of the nonincreasing sequence $(y_1,\dots,y_n)$. Expanding the square gives
$$\sum_{i=1}^{n}x_i^2+\sum_{i=1}^{n}z_i^2-2\sum_{i=1}^{n}x_i z_i.$$
Since $(z_i)$ is a permutation of $(y_i)$, the quantity $\sum z_i^2$ is fixed. Hence minimizing the original expression is equivalent to maximizing
$$\sum_{i=1}^{n}x_i z_i.$$
This suggests the rearrangement inequality. Before relying on it, it is useful to inspect small cases.
For $n=2$, the two possible permutations are $(y_1,y_2)$ and $(y_2,y_1)$. The difference between the corresponding scalar products equals
$$x_1y_1+x_2y_2-(x_1y_2+x_2y_1) =(x_1-x_2)(y_1-y_2),$$
which is nonnegative because both sequences are decreasing.
For $n=3$, starting from a permutation not equal to $(y_1,y_2,y_3)$, there must exist an inversion, namely indices $i<j$ with $z_i<z_j$. If those two entries are exchanged, the scalar product changes by
$$x_i z_j+x_j z_i-(x_i z_i+x_j z_j) =(x_i-x_j)(z_j-z_i)\ge 0.$$
Thus removing an inversion never decreases the scalar product. Repeatedly removing inversions eventually produces the ordered permutation $(y_1,\dots,y_n)$.
A direct proof by successive inversion removal appears simpler than quoting the rearrangement inequality. The delicate step is to verify exactly how the scalar product changes under a transposition correcting an inversion.
Problem Understanding
We are given two real sequences
$$x_1\ge x_2\ge\cdots\ge x_n, \qquad y_1\ge y_2\ge\cdots\ge y_n.$$
Among all permutations $(z_1,\dots,z_n)$ of the numbers $y_1,\dots,y_n$, we must prove that the quantity
$$\sum_{i=1}^{n}(x_i-z_i)^2$$
is smallest when the terms are matched in the same order, namely when $z_i=y_i$ for every $i$.
This is a Type B problem. The statement itself is the desired conclusion.
The objects involved are two ordered real sequences and all permutations of one of them. The difficulty is that the squared-distance expression contains many terms, and comparing different permutations directly is cumbersome. After expansion, the problem becomes a question about maximizing a scalar product. The crucial fact is that placing larger $y$-values opposite larger $x$-values produces the largest possible scalar product.
Proof Architecture
We shall prove the statement through two lemmas.
Lemma 1. If a permutation $(z_1,\dots,z_n)$ contains an inversion, that is, indices $i<j$ with $z_i<z_j$, then exchanging $z_i$ and $z_j$ does not decrease the scalar product $\sum x_k z_k$.
The reason is that the change in the scalar product equals $(x_i-x_j)(z_j-z_i)$, which is nonnegative.
Lemma 2. Among all permutations of $y_1,\dots,y_n$, the scalar product $\sum x_i z_i$ is maximized by the ordered permutation $(y_1,\dots,y_n)$.
The reason is that every permutation can be transformed into the ordered one by repeatedly removing inversions, and Lemma 1 shows that each such step does not decrease the scalar product.
After these lemmas, we expand the squares. The terms $\sum x_i^2$ and $\sum z_i^2$ are independent of the permutation, so minimizing the squared-distance sum is equivalent to maximizing the scalar product. Lemma 2 then yields the desired inequality.
The most delicate point is Lemma 1, because an incorrect computation of the change under a transposition would invalidate the whole argument.
Solution
Define
$$S(z_1,\dots,z_n)=\sum_{i=1}^{n}x_i z_i.$$
We begin with the key local comparison.
Lemma 1
Let $(z_1,\dots,z_n)$ be a permutation of $(y_1,\dots,y_n)$. Suppose there exist indices $i<j$ such that $z_i<z_j$. Let $(z_1',\dots,z_n')$ be obtained by exchanging $z_i$ and $z_j$. Then
$$S(z_1',\dots,z_n')\ge S(z_1,\dots,z_n).$$
Proof
All terms of the scalar product remain unchanged except those involving positions $i$ and $j$. Hence
$$\begin{aligned} S(z_1',\dots,z_n')-S(z_1,\dots,z_n) &=(x_i z_j+x_j z_i)-(x_i z_i+x_j z_j)\ &=(x_i-x_j)(z_j-z_i). \end{aligned}$$
Since $i<j$ and $x_1\ge x_2\ge\cdots\ge x_n$, we have
$$x_i\ge x_j.$$
By assumption,
$$z_j-z_i>0.$$
Consequently,
$$(x_i-x_j)(z_j-z_i)\ge0.$$
Thus
$$S(z_1',\dots,z_n')\ge S(z_1,\dots,z_n),$$
which proves the lemma. ∎
Certification. This lemma establishes that correcting a single inversion cannot decrease the scalar product; comparing entire permutations at once would obscure this exact quantitative change.
Lemma 2
Among all permutations $(z_1,\dots,z_n)$ of $(y_1,\dots,y_n)$, the maximum value of
$$S(z_1,\dots,z_n)$$
is attained when
$$(z_1,\dots,z_n)=(y_1,\dots,y_n).$$
Proof
Consider an arbitrary permutation $(z_1,\dots,z_n)$.
If it is already nonincreasing, then because it consists of exactly the numbers $y_1,\dots,y_n$, whose nonincreasing arrangement is
$$y_1\ge y_2\ge\cdots\ge y_n,$$
we must have
$$z_i=y_i$$
for every $i$.
Assume now that $(z_1,\dots,z_n)$ is not nonincreasing. Then there exists an inversion, namely indices $i<j$ with $z_i<z_j$. By Lemma 1, exchanging those two entries does not decrease the scalar product.
After the exchange, the number of inversions decreases by at least one. Since a permutation has only finitely many inversions, repeating this procedure finitely many times yields a nonincreasing permutation. Each step leaves the scalar product unchanged or increases it.
The final nonincreasing permutation must be
$$(y_1,\dots,y_n).$$
Hence
$$S(z_1,\dots,z_n)\le S(y_1,\dots,y_n).$$
Since the initial permutation was arbitrary, the ordered permutation maximizes the scalar product. ∎
Certification. This lemma establishes the global maximality of the ordered arrangement; skipping the inversion-elimination argument would leave unexplained why a local improvement leads to the global optimum.
We now prove the stated inequality.
For any permutation $(z_1,\dots,z_n)$ of $(y_1,\dots,y_n)$,
$$\begin{aligned} \sum_{i=1}^{n}(x_i-z_i)^2 &=\sum_{i=1}^{n}x_i^2+\sum_{i=1}^{n}z_i^2-2\sum_{i=1}^{n}x_i z_i. \end{aligned}$$
Because $(z_1,\dots,z_n)$ is a permutation of $(y_1,\dots,y_n)$,
$$\sum_{i=1}^{n}z_i^2=\sum_{i=1}^{n}y_i^2.$$
Therefore
$$\sum_{i=1}^{n}(x_i-z_i)^2 = \sum_{i=1}^{n}x_i^2+\sum_{i=1}^{n}y_i^2 -2S(z_1,\dots,z_n).$$
The first two sums are independent of the permutation. Consequently, minimizing
$$\sum_{i=1}^{n}(x_i-z_i)^2$$
is equivalent to maximizing
$$S(z_1,\dots,z_n).$$
By Lemma 2,
$$S(z_1,\dots,z_n)\le S(y_1,\dots,y_n).$$
Multiplying by $-2$ and adding the constant
$$\sum_{i=1}^{n}x_i^2+\sum_{i=1}^{n}y_i^2$$
gives
$$\sum_{i=1}^{n}(x_i-y_i)^2 \le \sum_{i=1}^{n}(x_i-z_i)^2.$$
This is exactly the required inequality.
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the computation in Lemma 1. Recomputing independently,
$$\begin{aligned} &(x_i z_j+x_j z_i)-(x_i z_i+x_j z_j)\ &=x_i(z_j-z_i)+x_j(z_i-z_j)\ &=(x_i-x_j)(z_j-z_i). \end{aligned}$$
The sign is positive because $x_i\ge x_j$ and $z_j>z_i$. A careless rearrangement could easily produce $(x_j-x_i)(z_j-z_i)$, reversing the conclusion.
The second delicate step is the assertion that repeated inversion removal reaches $(y_1,\dots,y_n)$. Every exchange removes at least the chosen inversion. Since the total number of inversions is a nonnegative integer, the process must terminate. When no inversion remains, the resulting permutation is nonincreasing. Because it contains exactly the multiset ${y_1,\dots,y_n}$ and the sequence $(y_i)$ is already arranged in nonincreasing order, the final permutation equals $(y_1,\dots,y_n)$. Omitting the termination argument would leave open the possibility of an infinite process.
The third delicate step is the reduction from the quadratic expression to the scalar product. Expanding gives
$$\sum(x_i-z_i)^2=\sum x_i^2+\sum z_i^2-2\sum x_i z_i.$$
The term $\sum z_i^2$ is constant because permutation preserves the multiset of entries. Forgetting this fact would make the optimization argument invalid.
Alternative Approaches
A different proof uses the rearrangement inequality. That theorem states that if
$$x_1\ge\cdots\ge x_n \quad\text{and}\quad y_1\ge\cdots\ge y_n,$$
then among all permutations $(z_i)$ of $(y_i)$, the quantity
$$\sum_{i=1}^{n}x_i z_i$$
is maximal when $z_i=y_i$ for all $i$. After expanding the squares, the problem immediately reduces to this theorem.
Another approach proceeds by induction on $n$. One first shows that in an optimal permutation the largest value $y_1$ must be paired with the largest value $x_1$. If $y_1$ were paired with some $x_j$, exchanging the positions of $y_1$ and the value paired with $x_1$ would decrease the total squared distance. After fixing the pair $(x_1,y_1)$, the problem reduces to the remaining $n-1$ terms. This yields a recursive proof. The inversion method is preferable because it gives a direct global argument and requires only one elementary computation.