1975 IMO Problems/Problem 1
Let be real numbers such that Prove that, if is any permutation of then
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.
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
It is only the most common way of rearrangement inequality after expanding and subtracting same terms.~bluesoul
|1975 IMO (Problems) • Resources|
|1 • 2 • 3 • 4 • 5 • 6||Followed by|
|All IMO Problems and Solutions|