IMO 1975 Problem 1

Proposed by: -
Verified: no
Verdicts: FAIL + PASS
Solve time: 15m43s

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

Consider small examples with $n = 2$ and $n = 3$ to gain intuition. For $n = 2$, let $x_1 \ge x_2$ and $y_1 \ge y_2$. There are only two permutations of $y_1, y_2$, either $(y_1, y_2)$ or $(y_2, y_1)$. Compute the sums:

$$(x_1 - y_1)^2 + (x_2 - y_2)^2 \quad \text{versus} \quad (x_1 - y_2)^2 + (x_2 - y_1)^2.$$

Expanding both sides yields

$$(x_1 - y_2)^2 + (x_2 - y_1)^2 - (x_1 - y_1)^2 - (x_2 - y_2)^2 = 2(x_1 - x_2)(y_1 - y_2) \ge 0.$$

Thus, the inequality holds, suggesting that matching the largest $x_i$ with the largest $y_i$ and so on minimizes the sum of squares. For $n = 3$, similar direct calculations indicate that any deviation from the aligned order increases the sum, hinting that a general rearrangement inequality is at play. The core difficulty is to prove this for arbitrary $n$ without assuming induction, by systematically comparing a given permutation to the sorted order. A promising approach is to consider adjacent transpositions and show that swapping elements that violate the order increases the sum.

Problem Understanding

We are asked to prove that, given two sequences of real numbers $x_1 \ge x_2 \ge \cdots \ge x_n$ and $y_1 \ge y_2 \ge \cdots \ge y_n$, the sum of squared differences is minimized when $y_i$ are not permuted, i.e., paired in the same decreasing order with $x_i$. The problem is Type B, a pure proof. The objects involved are real numbers, sequences, permutations, and the squared Euclidean distance. The difficulty arises because an arbitrary permutation may be complex, so a direct comparison seems infeasible; the key is to reduce the problem to elementary swaps that increase the sum.

Proof Architecture

Lemma 1: For $n=2$, if $x_1 \ge x_2$ and $y_1 \ge y_2$, then

$$(x_1 - y_1)^2 + (x_2 - y_2)^2 \le (x_1 - y_2)^2 + (x_2 - y_1)^2.$$

This follows from expanding both sides and observing the non-negativity of $2(x_1 - x_2)(y_1 - y_2)$.

Lemma 2: For any permutation $z_1, \dots, z_n$ of $y_1, \dots, y_n$, there exists a sequence of adjacent swaps reducing the number of inversions, each of which does not decrease the sum $\sum (x_i - z_i)^2$. This follows from the pairwise comparison in Lemma 1.

Main Claim: The sum $\sum_{i=1}^n (x_i - y_i)^2$ is minimal among all permutations of $y_i$. Proof follows by applying Lemma 2 iteratively until $z_i$ is in decreasing order, matching the $x_i$ sequence. The hardest step is to justify rigorously that each adjacent swap increases or leaves unchanged the sum, which requires careful algebra.

Solution

Lemma 1. Let $x_1 \ge x_2$ and $y_1 \ge y_2$ be real numbers. Then

$$(x_1 - y_1)^2 + (x_2 - y_2)^2 \le (x_1 - y_2)^2 + (x_2 - y_1)^2.$$

Proof. Compute

\begin{align*}

(x_1 - y_2)^2 + (x_2 - y_1)^2 - (x_1 - y_1)^2 - (x_2 - y_2)^2 &= (x_1^2 - 2x_1y_2 + y_2^2 + x_2^2 - 2x_2y_1 + y_1^2) \

&\quad - (x_1^2 - 2x_1y_1 + y_1^2 + x_2^2 - 2x_2y_2 + y_2^2) \

&= -2x_1y_2 - 2x_2y_1 + 2x_1y_1 + 2x_2y_2 \

&= 2(x_1 - x_2)(y_1 - y_2) \ge 0,

\end{align*}

because $x_1 - x_2 \ge 0$ and $y_1 - y_2 \ge 0$. This proves the inequality. ∎ This establishes the minimality of the aligned order for $n=2$.

Lemma 2. Let $z_1, \dots, z_n$ be any permutation of $y_1, \dots, y_n$. If there exists an adjacent pair $i$ such that $z_i < z_{i+1}$, then swapping $z_i$ and $z_{i+1}$ does not decrease $\sum_{j=1}^n (x_j - z_j)^2$.

Proof. Consider the partial sum involving these two indices:

$$(x_i - z_i)^2 + (x_{i+1} - z_{i+1})^2.$$

After swapping $z_i$ and $z_{i+1}$, the sum becomes

$$(x_i - z_{i+1})^2 + (x_{i+1} - z_i)^2.$$

By Lemma 1, since $x_i \ge x_{i+1}$ and $z_{i+1} \ge z_i$, we have

$$(x_i - z_i)^2 + (x_{i+1} - z_{i+1})^2 \le (x_i - z_{i+1})^2 + (x_{i+1} - z_i)^2.$$

Thus each adjacent swap of an out-of-order pair cannot decrease the sum. ∎ This establishes the monotonicity property needed for reducing inversions.

Main Argument. Let $z_1, \dots, z_n$ be any permutation of $y_1, \dots, y_n$. If $z_i \neq y_i$ for some $i$, then there exists at least one adjacent inversion $z_i < z_{i+1}$. Swap this pair to obtain a new sequence $z'_1, \dots, z'_n$ with strictly fewer inversions. By Lemma 2, the sum $\sum (x_i - z'_i)^2 \ge \sum (x_i - z_i)^2$. Repeat this process until $z_i = y_i$ for all $i$, that is, the permutation is sorted in decreasing order. At each step, the sum does not decrease, so the final sum with $z_i = y_i$ is minimal among all permutations. This proves the desired inequality.

This completes the proof. ∎

Verification of Key Steps

Lemma 1 was verified independently by expanding $(x_1 - y_2)^2 + (x_2 - y_1)^2 - (x_1 - y_1)^2 - (x_2 - y_2)^2$, giving $2(x_1 - x_2)(y_1 - y_2)$. Checking with $x_1 = 5, x_2 = 2, y_1 = 4, y_2 = 1$, the difference equals $2(5-2)(4-1) = 18 \ge 0$, confirming correctness. Lemma 2 relies only on Lemma 1 and the adjacency structure, which is valid for all $n \ge 2$ because each step considers exactly two elements and the base $n=2$ case holds.

Alternative Approaches

A direct approach uses induction on $n$. For $n=1$ the inequality is trivial. Assume it holds for $n-1$ and consider the largest element $x_1$. Matching it with the largest $y_i$ in any permutation maximizes reduction in the squared difference for the first term. Removing this pair reduces the problem to $n-1$ elements, where the induction hypothesis applies. This method is equivalent to the adjacent swap argument but requires formal induction machinery. The swap-based approach avoids complications with the base case and induction hypothesis bookkeeping, offering a clearer and fully algebraic proof.