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

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

(Created page with "==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...")
 
(One intermediate revision by one other user not shown)
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>
  
−
==Solution==
+
==Solution1==
−
{{solution}}
+
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
 +
==Notice==
 +
It is only the most common way of rearrangement inequality after expanding and subtracting same terms.~bluesoul
  
 
==See Also==
 
==See Also==

Revision as of 15:17, 19 December 2021

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

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

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1975_IMO_Problems/Problem_1&oldid=168054"