Skip to main content

Inequalities Still Exist!

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?
Let us first see why this inequality is true:

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


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).
See ya next time!
                                                                                                  Mihir. M. Kaskhedikar       


Popular posts from this blog

The importance of "intuition" in geometry

Hii everyone! Today I will be discussing a few geometry problems in which once you "guess" or "claim" the important things, then the problem can easily be finished using not-so-fancy techniques (e.g. angle chasing, power-of-point etc. Sometimes you would want to use inversion or projective geometry but once you have figured out that some particular synthetic property should hold, the finish shouldn't be that non trivial) This post stresses more about intuition rather than being rigorous. When I did these problems myself, I used freehand diagrams (not geogebra or ruler/compass) because I feel that gives a lot more freedom to you. By freedom, I mean, the power to guess. To elaborate on this - Suppose you drew a perfect  diagram on paper using ruler and compass, then you would be too rigid on what is true in the diagram which you drew. But sometimes that might just be a coincidence. e.g. Let's say a question says $D$ is a random point on segment $BC$, so maybe

LMAO Revenge

Continuing the tradition of past years, our seniors at the Indian IMO camp(an unofficial one happened this year) once again conducted LMAO, essentially ELMO but Indian. Sadly, only those who were in the unofficial IMOTC conducted by Pranav, Atul, Sunaina, Gunjan and others could participate in that. We all were super excited for the problems but I ended up not really trying the problems because of school things and stuff yet I solved problem 1 or so did I think. Problem 1:  There is a   grid of real numbers. In a move, you can pick any real number  ,  and any row or column and replace every entry   in it with  .  Is it possible to reach any grid from any other by a finite sequence of such moves? It turned out that I fakesolved and oh my god I was so disgusted, no way this proof could be false and then when I was asked Atul, it turns out that even my answer was wrong and he didn't even read the proof, this made me even more angry and guess what? I was not alone, Krutarth too fakesol

Edge querying in graph theory

In this post, I will present three graph theory problems in increasing difficulty, each with a common theme that one would determine a property of an edge in a complete graph through repeated iterations, and seek to achieve a greater objective. ESPR Summer Program Application: Alice and Bob play the following game on a $K_n$ ($n\ge 3$): initially all edges are uncolored, and each turn, Alice chooses an uncolored edge then Bob chooses to color it red or blue. The game ends when any vertex is adjacent to $n-1$ red edges, or when every edge is colored; Bob wins if and only if both condition holds at that time. Devise a winning strategy for Bob. This is more of a warm-up to the post, since it has a different flavor from the other two problems, and isn't as demanding in terms of experience with combinatorics. However, do note that when this problem was first presented, applicants did not know the winner ahead of time; it would be difficult to believe that Bob can hold such a strong