Art of Problem Solving
Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

1975 IMO Problems/Problem 1: Difference between revisions

← Older editNewer edit →
Pf02 (talk | contribs)
editor
415 edits
No edit summary
Pf02 (talk | contribs)
editor
415 edits
No edit summary
Line 50: Line 50:
"type 2" "moves" since the way they are used contradicts the
"type 2" "moves" since the way they are used contradicts the
fact that they are meant to be complementary.  Indeed, we can
fact that they are meant to be complementary.  Indeed, we can
not have only strict inequalities.
not have only strict inequalities.I suppose


The second issue is with the last paragraph.  Consider the
The second issue is with the last paragraph.  Consider the
sentences "Suppose that <math>x_a</math> is the biggest <math>x</math>-value that
sentences "Suppose that <math>x_a</math> is the biggest <math>x</math>-value that
is not paired with its <math>y</math>-value in the <math>x</math> and <math>z</math> pairing.
is not paired with its <math>y</math>-value in the <math>x</math> and <math>z</math> pairing.<cmath>\sum^n_{i=1}(x_i-y_i)^2\le\sum^n_{i=1}(x_i-z_i)^2.</cmath>
Then, switch this <math>y</math>-value with the <math>y</math>-value currently
Then, switch this <math>y</math>-value with the <math>y</math>-value currently
paired with <math>x_a</math>."  These two sentences do not make sense.
paired with <math>x_a</math>."  These two sentences do not make sense.
Line 94: Line 94:
that <math>\sigma(y_i) = y_j, \sigma(y_j) = y_i</math> and <math>\sigma(y_k) = y_k</math>
that <math>\sigma(y_i) = y_j, \sigma(y_j) = y_i</math> and <math>\sigma(y_k) = y_k</math>
for all <math>k \ne i, j</math>.  In other words, a transposition swaps two
for all <math>k \ne i, j</math>.  In other words, a transposition swaps two
elements of <math>S</math>, and leaves the others in place.
elements of <math>S</math>, and leaves the others in place. Remember that we
can combine permutations.  Explicitely, if <math>\sigma_1, \sigma_2</math>
are two permutations,
<math>\sigma_1 : \{y_i\} \rightarrow \{z_j\} = \{\sigma_1(y_i)\}</math> and
<math>\sigma_2 : \{z_j\} \rightarrow \{z_{k}^{(2)}\} = \{\sigma_2(z_j)\}</math>
then we have the combined permutation
<math>\sigma = \sigma_2 \circ \sigma_1</math> which is
<math>\sigma : \{y_i\} \rightarrow \{z_{k}^{(2)}\} = \{\sigma_2(\sigma_1((y_i))\}.</math>


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


We will call a transposition <math>\mathbf{adjacent}</math> if it swaps two
consecutive elements of <math>S</math>.  In other words <math>\sigma</math> is adjacent,
if it permutes <math>\{z_1, \dots, z_i, z_{i+1}, \dots, z_n\}</math> into
<math>\{z_1, \dots, z_{i+1}, z_i, \dots, z_n\}</math>.  We will call
a permutation <math>\mathbf{positive}</math> if given <math>i < j</math> and the elements
<math>z_i, z_j</math> being swapped, the inequality <math>z_i \ge z_j</math> is satisfied.
The statement of the problem will follow from the following two
lemmas:
<math>\mathbf{Lemma\ 1}</math>  If <math>\sigma</math> is a positive transposition
<math>\sigma : \{z_j\} \rightarrow \{z_{k}^{(2)}\} = \{\sigma(z_j)\}</math>
then <math>\sum^n_{i=1}(x_i - z_i)^2 \le \sum^n_{i=1}(x_i - z_i^{(2)})^2.</math>
<math>\mathbf{Lemma\ 2}</math>  Every permutation <math>\sigma</math> 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
<math>\sigma = \sigma_m \circ \sigma_{m-1} \circ \dots \circ \sigma_1</math>,
where each <math>\sigma_k</math> is an adjacent, positive permutation.  If
<math>\{z_i\}</math> is the resulting sequence from <math>\sigma</math> and
<math>\{z_i^{(k)}\}</math> are the resulting sequences from <math>\sigma_k</math> then
<math>z_i = z_i^{(m)}</math> for each <math>i</math>.  According to Lemma 1, using that
each <math>\sigma_k</math> is positive, we have
<math>\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.</math>
We will now prove the two lemmas.
<math>\mathbf{Proof\ of\ lemma\ 1}</math>




Revision as of 13:04, 4 November 2025

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 notions of "pairing" and "type 1 move" vs. "type 2 move" are not defined. This is particularly bad with "type 1" and "type 2" "moves" since the way they are used contradicts the fact that they are meant to be complementary. Indeed, we can not have only strict inequalities.I suppose

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.\[\sum^n_{i=1}(x_i-y_i)^2\le\sum^n_{i=1}(x_i-z_i)^2.\] 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 say.)

$\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

See Also

1975 IMO (Problems) • Resources
Preceded by
First Question 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 3
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1975_IMO_Problems/Problem_1&oldid=265042"