1975 IMO Problems/Problem 1: Difference between revisions

Revision as of 16:29, 3 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.

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 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.

TO BE CONTINUED

@@ Line 1: / Line 1: @@
 ==Problem==
 Let <math>x_i, y_i</math> <math>(i=1,2,\cdots,n)</math> be real numbers such that <cmath>x_1\ge x_2\ge\cdots\ge x_n \text{ and } y_1\ge y_2\ge\cdots\ge y_n.</cmath> Prove that, if <math>z_1, z_2,\cdots, z_n</math> is any permutation of <math>y_1, y_2, \cdots, y_n,</math> then <cmath>\sum^n_{i=1}(x_i-y_i)^2\le\sum^n_{i=1}(x_i-z_i)^2.</cmath>
 ==Video Solution(In Chinese)==
 https://youtu.be/3-iF4zIxsUQ
 ==Solution==
 We can expand and simplify the inequality a bit, and using the fact that <math>z</math> is a permutation of <math>y</math>, we can cancel some terms.
 <cmath>\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</cmath>
@@ Line 17: / Line 20: @@
 ~mathboy100
 ==Solution 2==
 We can rewrite the summation as
 <cmath>\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.</cmath>
@@ Line 29: / Line 34: @@
 is proved, which is equivalent to what we wanted to prove.
 <cmath> </cmath>
 ~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)==
+<math>\mathbf{1}</math>  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.
+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
+is not paired with its <math>y</math>-value in the <math>x</math> and <math>z</math> pairing.
+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.
+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 <math>x</math>-<math>y</math> pairing"
+is unclear: it is not clear that we would reach "the <math>x</math>-<math>y</math>
+pairing" (whatever "pairing" may mean).
+<math>\mathbf{2}</math>  Solution 2 is incorrect.  The author assumed
+that <math>x_pz_m</math> and <math>x_qz_n</math> are terms in <math>\sum^n_{i=1}x_iz_i</math>,
+but this is not true unless <math>p = m</math> and <math>q = n</math>.
+(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 <math>z_i</math>s that are not ordered in the form
+<math>z_1 \ge z_2 \ge \ldots \ge z_n</math> such that
+<math>\sum^n_{i=1}x_iz_i</math> is at a maximum out of all possible
+permutations and is greater than the sum <math>\sum^n_{i=1}x_iy_i</math>".
+But a benign and eager reader can guess what the author most
+likely wanted to say.)
+<math>\mathbf{3}</math>  The remark which follows the two "solutions" makes
+no sense at all.
+<math>\mathbf{4}</math>  Below I will give a solution to the problem.
+==Solution 3==
+Let <math>S = \{y_1, y_2, \cdots, y_n\}</math> be the given set of numbers,
+<math>y_1 \ge y_2 \ge \cdots \ge y_n</math>, and let <math>\{z_1, z_2, \cdots, z_n\}</math>
+be a permutation of the set <math>S</math>.  In other words <math>z_j = \sigma(y_i)</math>
+for a one-to-one function <math>\sigma: S \rightarrow S</math>.  Remember that
+a transposition is a permutation such that there exist <math>i, j</math> such
+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
+elements of <math>S</math>, and leaves the others in place.
+TO BE CONTINUED
 ==See Also==
 {{IMO box|year=1975|before=First Question|num-a=3}}
-[[Category:Olympiad Geometry Problems]]
+[[Category:Olympiad Algebra Problems]]

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