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 $2n$ reals $a_1,a_2,$...$,a_n$ and $b_1,b_2$...$,b_n$, $\forall i\leq j\leq n,$ $a_i\leq a_j$ and $b_i\leq b_j$. Consider any permutation $p$ on {$1,2,$.....$,n$}. Then
$$\sum_{i=1}^{i=n}a_ib_{n+1-i}\leq \sum_{i=1}^{i=n} a_ib_{p(i)}\leq \sum_{i=1}^{i=n}a_ib_i.$$
and equality for both inequalities holds when either all $a_i$'s or all $b_i$'s are the same.
To get an intuition of what the rearrangement inequality addresses, think over the following problems:
- There are $n$ construction companies and $n$ pieces of land of sizes $l_1,l_2,........,l_n$ 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 $c_1,c_2,.......,c_n$. How would you sell your land to gain maximum amount?
- You own a construction company and need to buy $n$ pieces of land of sizes $l_1,l_2,.......,l_n$ units for construction purposes from $n$ different land owners. Each of this land owner sell his land at amounts $c_1,c_2,........,c_n$ 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 $p$. Suppose there exist $i$ and $j$ such that $i<j$ and $p(i)>p(j)$. Create another permutation $p'$ such that $p'(i)=p(j),$ $p'(j)=p(i)$ and $p'(k)=p(k)\:\:\forall k\neq i,j.$ Then
$$\sum_{i=1}^{i=n}a_ib_{p'(i)}-\sum_{i=1}^{i=n}a_ib_{p(i)}=a_ib_{p(j)}+a_jb_{p(i)}-a_ib_{p(i)}-a_jb_{p(j)}=(a_j-a_i)(b_{p(i)}-b_{p(j)})\geq 0$$
The last inequality follows from the fact that $i\leq j$ and $p(j)\leq p(i)$ yield $a_i\leq a_j$ and $b_{p(j)}\leq b_{p(i)}.$
So this means that any $p$ containing at least one inversion: # number of pairs $(i,j)$ such that $i<j$ and $p(i)>p(j)$, cannot be the possible candidate for maximizing $\sum_{i=1}^{i=n} a_ib_{p(i)}$. So maximum can be achieved only for permutations with $0$ inversions, and there is exactly one of them namely the identity permutation. This establishes the second part of the rearrangement inequality.
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 $n$ positive reals $a_1,a_2,$......$,a_n$, $$\frac {\sum_{i=1}^{i=n}a_i}{n}\geq (\prod_{i=1}^{i=n}a_i)^{\frac{1}{n}}.$$
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 $f(x_1,x_2,$....$,x_n)\geq g(x_1,x_2,$....$,x_n)$ for which $\frac {f(tx_1,tx_2,...tx_n)}{f(x_1,x_2,...,x_n)}=\frac {g(tx_1,tx_2,....,tx_n)}{g(x_1,x_2,...,x_n)}=t^k$ for some integer $k$ and all reals $t$) attains a constant value, and proving the inequality for this case, the actual inequality can be proved by scaling the variables involved by a constant factor. So assume $\prod_{i=1}^{i=n}a_i=1$. Let $x_1,x_2,$.....$,x_n$ be arbitrary positive reals such that $a_i=\frac{x_i}{x_{i+1}}$ $\forall i<n$. Then by the normalization condition, $a_n=\frac{x_n}{x_1}$.
So it needs to be proven that $\frac{x_1}{x_2}+\frac{x_2}{x_3}+$......$\frac{x_n}{x_1}\geq n$.
Can you write $n$ as $\frac{x_1}{x_1}+\frac{x_2}{x_2}+$....$+\frac{x_n}{x_n}$? Do you see the rearrangement inequality hidden somewhere?
So consider a permutation $p$ on {$1,2,$.....$,n$} such that $x_{p(i)}\leq x_{p(j)}$ for $i\leq j$.
Let $a_i=x_{p(i)}$ and $b_i=\frac{1}{x_{p(n+1-i)}}$. Then for $i\leq j$, $a_i\leq a_j$ and $b_i\leq b_j$.
So applying the first part of the rearrangement inequality on $a_i$ and $b_i$, the lower bound on $\sum_{i=1}^{i=n}\frac{x_i}{x_{q(i)}}$ for any permutation $q$ is $\sum_{i=1}^{i=n} a_ib_{n+1-i}=\sum_{i=1}^{i=n} \frac{x_{p(i)}}{x_{p(i)}}=n.$
So now just take $q(1)=2$, $q(2)=3,$......$q(n)=1$ and the proof is completed $\blacksquare$
Inequality 2: Generalized Nesbitt's inequality
Given $n$ positive reals $x_1,x_2,.....,x_n$, let $s=x_1+x_2+......+x_n$. We need to prove
$$\sum_{i=1}^{i=n} \frac{x_i}{s-x_i}\geq \frac{n}{n-1}.$$
WLOG assume $x_1\leq x_2\leq.......\leq x_n$. Then $s-x_1\geq s-x_2.......\geq s-x_n$ and $\frac{1}{s-x_1}\leq \frac{1}{s-x_2}\leq .......\leq \frac{1}{s-x_n}$. So let $b_i=x_i$ and $a_i=\frac{1}{s-x_i}$.
Now consider $n-1$ permutations $p_1,p_2,.....,p_{n-1}$ such that
$p_i(x)=(x+i-1)$(mod$\:n)+1$.
By the second part of rearrangement inequality, $$\sum_{j=1}^{j=n-1}\sum_{i=1}^{i=n} a_ib_{p_j(i)}\leq (n-1)\sum_{i=1}^{i=n} a_ib_i= (n-1)\sum_{i=1}^{i=n} \frac{x_i}{s-x_i}$$
$$\sum_{j=1}^{j=n-1}\sum_{i=1}^{i=n} a_ib_{p_j(i)}=\sum_{i=1}^{i=n}a_i(\sum_{j=1}^{j=n-1}b_{p_j(i)})=\sum_{i=1}^{i=n}\frac{1}{s-x_i}(s-x_i)=n.$$
Thus we get $\sum_{i=1}^{i=n} \frac{x_i}{s-x_i}\geq \frac{n}{n-1}$ $\blacksquare$
Inequality 3: Chebyshev's inequality
Given $2n$ positive reals $a_1,a_2,......,a_n$ and $b_1.b_2.......,b_n$, $\forall i\leq j\:\:a_i\leq a_j$ and $b_i\leq b_j$. We need to prove
$$n(\sum_{i=1}^{i=n}a_ib_i)\geq (\sum_{i=1}^{i=n}a_i)(\sum_{i=1}^{i=n}b_i)\geq n(\sum_{i=1}^{i=n}a_ib_{n+1-i})$$
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 $p_i(x)=(x+i-1)$ (mod$\:n)\:+1$. Then $$(\sum_{i=1}^{i=n}a_i)(\sum_{i=1}^{i=n}b_i)=\sum_{j=1}^{j=n}\sum_{i=1}^{i=n}a_ib_{p_j(i)}$$
And by Rearrangement Inequality,
$$n\sum_{i=1}^{i=n}a_ib_{n+1-i}\leq \sum_{j=1}^{j=n}\sum_{i=1}^{i=n} a_ib_{p_j(i)}\leq n\sum_{i=1}^{i=n}a_ib_i\:\:\:\blacksquare$$
Now let's solve some problems that would help understand different applications of this beautiful inequality:
Problem 1:
Let $a,b$ and $c$ be positive reals. Prove that $\frac{max(a,b,c)}{min(a,b,c)}+\frac{min(a,b,c)}{max(a,b,c)}\geq \frac{a+b+c}{\sqrt[3]{abc}}-1$
Solution: WLOG let $a\geq b\geq c$. So $\frac{1}{c}\geq \frac{1}{b}\geq \frac{1}{a}$. By Chebyshev's inequality,$$3(\frac{a}{c}+\frac{b}{b}+\frac{c}{a})\geq (a+b+c)(\frac{1}{a}+\frac{1}{b}+\frac{1}{c}).$$
Now by AM-GM inequality, $$(a+b+c)(\frac{1}{a}+\frac{1}{b}+\frac{1}{c})\geq 3\frac{(a+b+c)}{\sqrt[3]{abc}}$$
Combining the above $2$ inequalities and noting that $a=max(a,b,c)$ and $c=min(a,b,c)$, we are done $\blacksquare$
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 $a_1,a_2,.......,a_n$ be $n$ distinct positive integers. Prove that $\sum_{i=1}^{i=n}\frac{a_i}{i^2}\geq \sum_{i=1}^{i=n}\frac{1}{i}$.
Solution: Consider a permutation $p$ on {$1,2,......,n$} such that $\forall i\leq j\leq n$, $a_{p(i)}\leq a_{p(j)}$ (basically define an ordering on $a_i$). So $a_{p(n)}\geq a_{p(n-1)}\geq......\geq a_{p(1)}$ and $\frac{1}{1^2}\geq \frac{1}{2^2}........\geq\frac{1}{n^2}$. Thus by the first part of the Rearrangement Inequality,
$$\sum_{i=1}^{i=n}\frac{a_i}{i^2}\geq\sum_{i=1}^{i=n} \frac{a_{p(i)}}{i^2}$$
Now consider the first condition of the problem statement. What can we say if $a_i$'s are distinct positive integers? $a_{p(i)}\geq i$ !!
$$\therefore \sum_{i=1}^{i=n}\frac{a_{p(i)}}{i^2}\geq \sum_{i=1}^{i=n} \frac{i}{i^2}=\sum_{i=1}^{i=n} \frac{1}{i}$$
Combining the two inequalities, we get the desired result $\blacksquare$
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 $p$ is and what values $a_i$ take, you just need to know what matchings of $a_i$ and $\frac{1}{i^2}$ would give the minimum sum and then use a given condition of the problem in the final step.
Problem 3:
Let $a,b$ and $c$ be positive reals. Prove that $$\frac{a^2+bc}{b+c}+\frac{b^2+ac}{a+c}+\frac{c^2+ab}{a+b}\geq a+b+c$$
Solution: Due to the symmetry present in the inequality, WLOG assume that $a\geq b\geq c$.
Thus, $a^2\geq b^2\geq c^2$ and $\frac{1}{b+c}\geq \frac{1}{a+c} \geq \frac{1}{a+b}$.
Applying part $2$ of the rearrangement inequality, $\frac{a^2}{b+c}+ \frac{b^2}{c+a}+\frac{c^2}{a+b} \geq \frac{b^2}{b+c}+\frac{c^2}{c+a}+\frac{a^2}{a+b}$
$$\therefore \frac{a^2+bc}{b+c}+\frac{b^2+ca}{c+a}+\frac{c^2+ab}{a+b}\geq \frac{b^2+bc}{b+c}+\frac{c^2+ca}{c+a}+\frac{a^2+ab}{a+b}=a+b+c\:\: \blacksquare$$
Comment: For inequalities involving $3$ variables and some cyclic summations of fractions, check if under any order on the variables whether it is an extreme value of RI. Examples of such expressions are $\frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b}$ where for any relative ordering of $a,b$ and $c$, this appears as the maximum value in the RI where we are pairing terms of the form $a$ and $\frac{1}{b+c}$. Another example is $a^2(b+c)+b^2(c+a)+c^2(a+b)$ where for any relative ordering of $a,b$ and $c$ it appears as the minimum value in the RI where we are pairing terms of the form $a^2$ and $b+c$. In the above problem, we assumed $a\geq b\geq c$, but by this we can't comment on the relative ordering of $a^2+bc$ and likewise terms. But by this we can indeed deduce the relative ordering of terms $a^2$ and likewise and $\frac{1}{b+c}$ and likewise. So we try to play around by pairing these terms and the solution follows by later observing that we needed to add the terms $\frac{bc}{b+c}$,$\frac{ca}{c+a}$ and $\frac{ab}{a+b}$ to both sides to get the desired inequality.
Problem 4:
Let $a$,$b$ and $c$ be positive reals. Prove that $$\frac{a+b}{b+c}+\frac{b+c}{c+a}+\frac{c+a}{a+b}\leq \frac{(a+b+c)^2}{ab+bc+ca}$$
Solution: Multiplying both sides by $(ab+bc+ca)$ and cancelling out some terms it needs to be proven that $$\frac{bc(a+b)}{b+c}+\frac{ca(b+c)}{c+a}+\frac{ab(c+a)}{a+b}\leq ab+bc+ca.$$ Note that the inequality we need to prove is not symmetric in $a,b$ and $c$. That is if we denote by $P(a,b,c)$ the assertion of the inequality, then $P(a,b,c) \neq P(b,a,c)$. But it is cyclic as $P(a,b,c)=P(b,c,a)=P(c,a,b)$. So we can indeed WLOG assume that $a=max(a,b,c)$. Thus we only need to consider $2$ cases on the relative ordering of $a,b$ and $c$.
- $a\geq b\geq c$
Thus $\frac{1}{b}+\frac{1}{c}\geq \frac{1}{c}+\frac{1}{a}\geq\frac{1}{a}+\frac{1}{b}\Rightarrow \frac{ab}{a+b}\geq \frac{ca}{c+a}\geq \frac{bc}{b+c}$
Also $a+b\geq c+a\geq b+c$. Thus by second part of RI, $$\frac{ab(a+b)}{a+b}+\frac{ca(c+a)}{c+a}+\frac{bc(b+c)}{b+c}\geq \frac{ab(c+a)}{a+b}+\frac{ca(b+c)}{c+a}+\frac{bc(a+b)}{b+c}$$
- $a\geq c\geq b$
Thus $\frac{1}{b}+\frac{1}{c}\geq \frac{1}{a}+\frac{1}{b}\geq \frac{1}{c}+\frac{1}{a}\Rightarrow \frac{ca}{c+a}\geq \frac{ab}{a+b}\geq \frac{bc}{b+c}$
Also $c+a\geq a+b\geq b+c$. Thus by the second part of RI, $$\frac{ca(c+a)}{c+a}+\frac{ab(a+b)}{a+b}+\frac{bc(b+c)}{b+c}\geq \frac{ca(b+c)}{c+a}+\frac{ab(c+a)}{a+b}+\frac{bc(a+b)}{b+c}$$
Thus the inequality is proved $\blacksquare$
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