Difference between revisions of "1975 IMO Problems/Problem 1"
| Line 2: | Line 2: | ||
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> | 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> | ||
| − | == | + | ==Solution1== |
We can rewrite the summation as | 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> | <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 14: | Line 14: | ||
<cmath> </cmath> | <cmath> </cmath> | ||
~Imajinary | ~Imajinary | ||
| + | ==Notice== | ||
| + | It is only the most common way of rearrangement inequality after expanding and subtracting same terms.~bluesoul | ||
| + | |||
==See Also== | ==See Also== | ||
{{IMO box|year=1975|before=First Question|num-a=3}} | {{IMO box|year=1975|before=First Question|num-a=3}} | ||
[[Category:Olympiad Geometry Problems]] | [[Category:Olympiad Geometry Problems]] | ||
Revision as of 14:17, 19 December 2021
Contents
Problem
Let 
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.\]](http://latex.artofproblemsolving.com/2/9/8/2986cacba9b25b367eec05bc85a10139b47e70ee.png)
Prove that, if 
is any permutation of 
then ![\[\sum^n_{i=1}(x_i-y_i)^2\le\sum^n_{i=1}(x_i-z_i)^2.\]](http://latex.artofproblemsolving.com/7/d/2/7d2ec052f76e524fbdaf5010c1b49882e5278b00.png)
Solution1
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.\]](http://latex.artofproblemsolving.com/6/f/6/6f616207472ba6ac6b2653211c1fab12444e29be.png)
Since 
, the above inequality is equivalent to
![\[\sum^n_{i=1}x_iy_i \ge \sum^n_{i=1}x_iz_i.\]](http://latex.artofproblemsolving.com/1/8/6/186cb2d69a67a36be1eb86fd2583c9658e9a35a9.png)
We will now prove that the left-hand side of the inequality is the greatest sum reached out of all possible values of 
. Obviously, if 
or 
, the inequality is true. Now, assume, for contradiction, that neither of those conditions are true and that there exists some order of 
s that are not ordered in the form 
such that is at a maximum out of all possible permutations and is greater than the sum 
. This necessarily means that in the sum there exists two terms 
and 
such that 
and 
. Notice that
![\[x_pz_n + x_qz_m - (x_pz_m + x_qz_n) = (x_p-x_q)(z_n-z_m) > 0,\]](http://latex.artofproblemsolving.com/0/9/b/09be8e904b29cf0c79ac821b93d1bc7336bd5ad2.png)
which means if we make the terms 
and 
instead of the original and , 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\]](http://latex.artofproblemsolving.com/0/a/7/0a7fe76954296fa4754734c7ebd1853e0e00fcdc.png)
is proved, which is equivalent to what we wanted to prove.
![\[\]](http://latex.artofproblemsolving.com/5/7/f/57f1406b65f9f2e6a365b7356da731780b42cceb.png)
~Imajinary
Notice
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 | ||
