1975 IMO Problems/Problem 1

Problem

Let $x_i, y_i$ $(i=1,2,\cdots,n)$ be real numbers such that $x_1\ge x_2\ge\cdots\ge x_n \text{ and } y_1\ge y_2\ge\cdots\ge 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^n_{i=1}(x_i-y_i)^2\le\sum^n_{i=1}(x_i-z_i)^2.$

Video Solution(In Chinese)

https://youtu.be/3-iF4zIxsUQ

Solution

We can expand and simplify the inequality a bit, and using the fact that $z$ is a permutation of $y$ , we can cancel some terms. $\sum^n_{i=1}x_i^2 + \sum^n_{i=1}y_i^2 - 2\sum^n_{i=1}x_iy_i \leq \sum^n_{i=1}x_i^2 + \sum^n_{i=1}z_i^2 - 2\sum^n_{i=1}x_iz_i$ $\sum^n_{i=1}x_iy_i \geq \sum^n_{i=1}x_iz_i$ Consider the pairing $x_1 \rightarrow y_1$ , $x_2 \rightarrow y_2$ , ... $x_n \rightarrow y_n$ . By switching around some of the $y$ values, we have obtained the pairing $x_1 \rightarrow z_1$ , $x_2 \rightarrow z_2$ , ... $x_n \rightarrow z_n$ . Suppose that we switch around two $y$ -values, $y_m$ and $y_n$ , such that $y_m > y_n$ . If $x_m > x_n$ , call this a type 1 move. Otherwise, call this a type 2 move.

Type 2 moves only increase the sum of the products of the pairs. The sum is increased by $x_n \cdot y_m + x_m \cdot y_n - x_m \cdot y_m - x_n \cdot y_n$ . This is equivalent to $(x_n - x_m)(y_m - y_n)$ , which is clearly nonnegative since $y_m > y_n$ and $x_n > x_m$ .

We will now consider switching from the $x$ - $z$ pairing back to the $x$ - $y$ pairing. We will prove that from any pairing of $x$ and $z$ values, you can use just type 2 moves to navigate back to the pairing of $x$ and $y$ values, which will complete the proof.

Suppose that $x_a$ is the biggest $x$ -value that is not paired with its $y$ -value in the $x$ and $z$ pairing. Then, switch this $y$ -value with the $y$ -value currently paired with $x_a$ . This is obviously a type 2 move. Continue this process until you reach back to the $x$ - $y$ pairing. All moves are type 2 moves, so the proof is complete.

~mathboy100

Solution 2

We can rewrite the summation as $\sum^n_{i=1} x_i^2 + \sum^n_{i=1} y_i^2 - \sum^n_{i=1}x_iy_i \le \sum^n_{i=1} x_i^2 + \sum^n_{i=1} z_i^2 - \sum^n_{i=1}x_iz_i.$ Since $\sum^n_{i=1} y_i^2 = \sum^n_{i=1} z_i^2$ , the above inequality is equivalent to $\sum^n_{i=1}x_iy_i \ge \sum^n_{i=1}x_iz_i.$ We will now prove that the left-hand side of the inequality is the greatest sum reached out of all possible values of $\sum^n_{i=1}x_iz_i$ . Obviously, if $x_1 = x_2 = \ldots = x_n$ or $y_1 = y_2 = \ldots = y_n$ , the inequality is true. Now, assume, for contradiction, that neither of those conditions are true and that there exists some order of $z_i$ s that are not ordered in the form $z_1 \ge z_2 \ge \ldots \ge z_n$ such that $\sum^n_{i=1}x_iz_i$ is at a maximum out of all possible permutations and is greater than the sum $\sum^n_{i=1}x_iy_i$ . This necessarily means that in the sum $\sum^n_{i=1}x_iz_i$ there exists two terms $x_pz_m$ and $x_qz_n$ such that $x_p > x_q$ and $z_m < z_n$ . Notice that $x_pz_n + x_qz_m - (x_pz_m + x_qz_n) = (x_p-x_q)(z_n-z_m) > 0,$ which means if we make the terms $x_pz_n$ and $x_qz_m$ instead of the original $x_pz_m$ and $x_qz_n$ , we can achieve a higher sum. However, this is impossible, since we assumed we had the highest sum. Thus, the inequality $\sum^n_{i=1}x_iy_i \ge \sum^n_{i=1}x_iz_i$ is proved, which is equivalent to what we wanted to prove. $\[\]$

~Imajinary

Remark

It is only the most common way of rearrangement inequality after expanding and subtracting same terms.~bluesoul

Remarks (added by pf02, November 2025)

$\mathbf{1}$ The first solution can not be called a solution. There are several issues with it. The first issue is that the notion of "pairing" is not defined. The notions "type 1 move" vs. "type 2 move" are defined only very loosely. The way they are used contradicts the fact that they are meant to be complementary. Indeed, we can not assume we have only strict inequalities among the $x$ 's and the $y$ 's.

The second issue is with the last paragraph. Consider the sentences "Suppose that $x_a$ is the biggest $x$ -value that is not paired with its $y$ -value in the $x$ and $z$ pairing. Then, switch this $y$ -value with the $y$ -value currently paired with $x_a$ ." These two sentences do not make sense. Furthermore, depending on what meaning we would want to force on these two sentences, and on what "type 2 move" may mean, the sentence which follows, "This is obviously a type 2 move" may or may not be true. And finally, the sentence "Continue this process until you reach back to the $x$ - $y$ pairing" is unclear: it is not clear that we would reach "the $x$ - $y$ pairing" (whatever "pairing" may mean).

$\mathbf{2}$ Solution 2 is incorrect. The author assumed that $x_pz_m$ and $x_qz_n$ are terms in $\sum^n_{i=1}x_iz_i$ , but this is not true unless $p = m$ and $q = n$ .

(Never mind the fact that there is a crucial sentence which does not make sense: "assume, for contradiction, that neither of those conditions are true and that there exists some order of $z_i$ s that are not ordered in the form $z_1 \ge z_2 \ge \ldots \ge z_n$ such that $\sum^n_{i=1}x_iz_i$ is at a maximum out of all possible permutations and is greater than the sum $\sum^n_{i=1}x_iy_i$ ". But a benign and eager reader can guess what the author most likely wanted to express in this sentence.)

$\mathbf{3}$ The remark which follows the two "solutions" makes no sense at all.

$\mathbf{4}$ Below I will give a solution to the problem.

Solution 3

Let $S = \{y_1, y_2, \cdots, y_n\}$ be the given set of numbers, $y_1 \ge y_2 \ge \cdots \ge y_n$ , and let $\{z_1, z_2, \cdots, z_n\}$ be a permutation of the set $S$ . In other words $z_j = \sigma(y_i)$ for a one-to-one function $\sigma: S \rightarrow S$ . Remember that a transposition is a permutation such that there exist $i, j$ such that $\sigma(y_i) = y_j, \sigma(y_j) = y_i$ and $\sigma(y_k) = y_k$ for all $k \ne i, j$ . In other words, a transposition swaps two elements of $S$ , and leaves the others in place. Remember that we can combine permutations. Explicitely, if $\sigma_1, \sigma_2$ are two permutations, $\sigma_1 : \{y_i\} \rightarrow \{z_j\} = \{\sigma_1(y_i)\}$ and $\sigma_2 : \{z_j\} \rightarrow \{z_{k}^{(2)}\} = \{\sigma_2(z_j)\}$ then we have the combined permutation $\sigma = \sigma_2 \circ \sigma_1$ which is $\sigma : \{y_i\} \rightarrow \{z_{k}^{(2)}\} = \{\sigma_2(\sigma_1((y_i))\}.$

For the purposes of the solution to this problem, we will think of the elements of the set $S$ as arranged in a sequence, specifically, the sequence created by the last permutation applied. For example if we swap $10$ and $22$ in the set (or sequence) $\{27, 22, 14, 10, 8, 5\}$ , the new set (or sequence) will be $\{27, 10, 14, 22, 8, 5\}$ . This way, each element in the permuted set has a precisely defined index.

We will call a transposition $\mathbf{adjacent}$ if it swaps two consecutive elements of $S$ . In other words $\sigma$ is adjacent, if it permutes $\{z_1, \dots, z_i, z_{i+1}, \dots, z_n\}$ into $\{z_1, \dots, z_{i+1}, z_i, \dots, z_n\}$ . We will call a permutation $\mathbf{positive}$ if given $i < j$ and the elements $z_i, z_j$ being swapped, the inequality $z_i \ge z_j$ is satisfied.

The statement of the problem will follow from the following two lemmas:

$\mathbf{Lemma\ 1}$ If $\sigma$ is a positive transposition $\sigma : \{z_j\} \rightarrow \{z_{k}^{(2)}\} = \{\sigma(z_j)\}$ then $\sum^n_{i=1}(x_i - z_i)^2 \le \sum^n_{i=1}(x_i - z_i^{(2)})^2.$

$\mathbf{Lemma\ 2}$ Every permutation $\sigma$ is the combination of adjacent, positive transpositions.

Let us prove the problem assuming the lemmas. According to Lemma 2, we can write a given permutation as $\sigma = \sigma_m \circ \sigma_{m-1} \circ \dots \circ \sigma_1$ , where each $\sigma_k$ is an adjacent, positive permutation. If $\{z_i\}$ is the resulting sequence from $\sigma$ and $\{z_i^{(k)}\}$ are the resulting sequences from $\sigma_k$ then $z_i = z_i^{(m)}$ for each $i$ . According to Lemma 1, using that each $\sigma_k$ is positive, we have

$\sum^n_{i=1}(x_i - y_i)^2 \le \sum^n_{i=1}(x_i - z_i^{(1)})^2 \le \sum^n_{i=1}(x_i - z_i^{(2)})^2 \le \dots \le \sum^n_{i=1}(x_i - z_i^{(m)})^2 = \sum^n_{i=1}(x_i - z_i)^2.$

We will now prove the two lemmas.

$\mathbf{Proof\ of\ lemma\ 1}$

TO BE CONTINUED

1975 IMO (Problems) • Resources
Preceded by First Question	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 3
All IMO Problems and Solutions

Page

Toolbox

Search