Long time no inequality post right? So, this is going to be an introductory post on the Rearrangement Inequality. During my Olympiad journey, Rearrangement Inequality was the one that I found most intuitive as well as beautiful. You might say that it is just a mathematical generalization of some idea that you kind of already know and might have used in some of your daily life optimizations, So it says this:
Given
and equality for both inequalities holds when either all
To get an intuition of what the rearrangement inequality addresses, think over the following problems:
- There are
construction companies and pieces of land of sizes units. You are the owner of all these lands and you need to sell a piece of land to each of these companies that give a fixed amount per unit of land and these amounts are . How would you sell your land to gain maximum amount? - You own a construction company and need to buy
pieces of land of sizes units for construction purposes from different land owners. Each of this land owner sell his land at amounts per unit respectively and you, intending to keep good relations with these land owners, need to buy a piece of land from each of them. What minimum amount you would need to pay for getting the required land?
Proof of the inequality:
We use a constructive argument to prove both bounds.
Consider any permutation
The last inequality follows from the fact that
So this means that any
The first part of the inequality has verbatim proof except for some minor tweaks. Can you guess where?
Now we see some of the magical applications of Rearrangement inequality in proving other inequalities.
Inequality 1: AM-GM inequality
We need to prove that for
Here we make use of a technique called normalization. It's really simple, it just assumes that some term in a homogenous inequality ( an inequality
So it needs to be proven that
Can you write
So consider a permutation
Let
So applying the first part of the rearrangement inequality on
So now just take
Inequality 2: Generalized Nesbitt's inequality
Given
WLOG assume
Now consider
By the second part of rearrangement inequality,
Thus we get
Inequality 3: Chebyshev's inequality
Given
Some readers might say that this is obvious given the previous two proofs they have seen and yeah it is.
As in inequality 2 let
And by Rearrangement Inequality,
Now let's solve some problems that would help understand different applications of this beautiful inequality:
Problem 1:
Let
Solution: WLOG let
Now by AM-GM inequality,
Combining the above
Comment: The problem became trivial after the direct application of Chebyshev's inequality. In olympiad problems, you might encounter Chebyshev's Inequality more than Rearrangement Inequality but as you have seen above the latter is a more powerful inequality.
Problem 2:
Let
Solution: Consider a permutation
Now consider the first condition of the problem statement. What can we say if
Combining the two inequalities, we get the desired result
Comment: This was an old IMO problem. The power of the Rearrangement Inequality can be seen here. You don't even care what the permutation
Problem 3:
Let
Solution: Due to the symmetry present in the inequality, WLOG assume that
Thus,
Applying part
Comment: For inequalities involving
Problem 4:
Let
Solution: Multiplying both sides by
Thus
Also
Thus
Also
Thus the inequality is proved
Comment: Note that the proof of both the cases that we took was hardly any different. But it is important to know when an inequality is symmetric and when it isn't. In inequalities that are not symmetric we need to consider all orderings while applying RI, in the case it is cyclic we can fix some quantity to be the maximum or minimum or something else.
So this it for this blog, if any doubts feel free to write it in the comments. Also for further reading on Rearrangement Inequality and inequalities in general, you can read the following books:
- Problem Solving Strategies by Arthur Engel (great book for getting introduced to inequalities).
- Secrets in Inequalities Vol 1 and 2 by Pham Kim Hung (has exhaustive problems on inequalities).
- Problems from the Book by Titu Andreescu and Gabriel Dospinescu (has some chapters on Olympiad Inequalities, contains really tough problems).
Comments
Post a Comment