Difference between revisions of "1975 IMO Problems/Problem 1"

Latest revision as of 00:00, 10 December 2022

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

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

@@ Line 3: / Line 3: @@
 ==Solution==
-{{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>
+<cmath>\sum^n_{i=1}x_iy_i \geq \sum^n_{i=1}x_iz_i</cmath>
+Consider the pairing <math>x_1 \rightarrow y_1</math>, <math>x_2 \rightarrow y_2</math>, ... <math>x_n \rightarrow y_n</math>. By switching around some of the <math>y</math> values, we have obtained the pairing <math>x_1 \rightarrow z_1</math>, <math>x_2 \rightarrow z_2</math>, ... <math>x_n \rightarrow z_n</math>. Suppose that we switch around two <math>y</math>-values, <math>y_m</math> and <math>y_n</math>, such that <math>y_m > y_n</math>. If <math>x_m > x_n</math>, 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 <math>x_n \cdot y_m + x_m \cdot y_n - x_m \cdot y_m - x_n \cdot y_n</math>. This is equivalent to <math>(x_n - x_m)(y_m - y_n)</math>, which is clearly nonnegative since <math>y_m > y_n</math> and <math>x_n > x_m</math>.
+We will now consider switching from the <math>x</math>-<math>z</math> pairing back to the <math>x</math>-<math>y</math> pairing. We will prove that from any pairing of <math>x</math> and <math>z</math> values, you can use just type 2 moves to navigate back to the pairing of <math>x</math> and <math>y</math> values, which will complete the proof.
+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>. This is obviously a type 2 move. Continue this process until you reach back to the <math>x</math>-<math>y</math> pairing. All moves are type 2 moves, so the proof is complete.
+~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>
+Since <math>\sum^n_{i=1} y_i^2 = \sum^n_{i=1} z_i^2</math>, the above inequality is equivalent to
+<cmath>\sum^n_{i=1}x_iy_i \ge \sum^n_{i=1}x_iz_i.</cmath>
+We will now prove that the left-hand side of the inequality is the greatest sum reached out of all possible values of <math>\sum^n_{i=1}x_iz_i</math>. Obviously, if <math>x_1 = x_2 = \ldots = x_n</math> or <math>y_1 = y_2 = \ldots = y_n</math>, the inequality is true. Now, 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>. This necessarily means that in the sum <math>\sum^n_{i=1}x_iz_i</math> there exists two terms <math>x_pz_m</math> and <math>x_qz_n</math> such that <math>x_p > x_q</math> and <math>z_m < z_n</math>. Notice that
+<cmath>x_pz_n + x_qz_m - (x_pz_m + x_qz_n) = (x_p-x_q)(z_n-z_m) > 0,</cmath>
+which means if we make the terms <math>x_pz_n</math> and <math>x_qz_m</math> instead of the original <math>x_pz_m</math> and <math>x_qz_n</math>, we can achieve a higher sum. However, this is impossible, since we assumed we had the highest sum. Thus, the inequality
+<cmath>\sum^n_{i=1}x_iy_i \ge \sum^n_{i=1}x_iz_i</cmath>
+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
 ==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

Page

Toolbox

Search