Difference between revisions of "1975 IMO Problems/Problem 1"
Mathboy100 (talk | contribs) |
Bobwang001 (talk | contribs) (Ph.D degree, https://www.youtube.com/@math000) |
||
(2 intermediate revisions by one other user not shown) | |||
Line 1: | Line 1: | ||
==Problem== | ==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> | 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== | ==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. | 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^ | + | <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^ | + | <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. | 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. | ||
Latest revision as of 11:21, 3 January 2025
Problem
Let
be real numbers such that
Prove that, if
is any permutation of
then
Video Solution(In Chinese)
Solution
We can expand and simplify the inequality a bit, and using the fact that is a permutation of
, we can cancel some terms.
Consider the pairing
,
, ...
. By switching around some of the
values, we have obtained the pairing
,
, ...
. Suppose that we switch around two
-values,
and
, such that
. If
, 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 . This is equivalent to
, which is clearly nonnegative since
and
.
We will now consider switching from the -
pairing back to the
-
pairing. We will prove that from any pairing of
and
values, you can use just type 2 moves to navigate back to the pairing of
and
values, which will complete the proof.
Suppose that is the biggest
-value that is not paired with its
-value in the
and
pairing. Then, switch this
-value with the
-value currently paired with
. This is obviously a type 2 move. Continue this process until you reach back to the
-
pairing. All moves are type 2 moves, so the proof is complete.
~mathboy100
Solution 2
We can rewrite the summation as
Since
, the above inequality is equivalent to
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
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
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
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 |