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 a1,a2,...,an and b1,b2...,bn, ijn, aiaj and bibj. Consider any permutation p on {1,2,.....,n}. Then

i=1i=naibn+1ii=1i=naibp(i)i=1i=naibi.

and equality for both inequalities holds when either all ai's or all bi'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 l1,l2,........,ln 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 c1,c2,.......,cn. 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 l1,l2,.......,ln units for construction purposes from n different land owners. Each of this land owner sell his land at amounts c1,c2,........,cn 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)ki,j. Then

i=1i=naibp(i)i=1i=naibp(i)=aibp(j)+ajbp(i)aibp(i)ajbp(j)=(ajai)(bp(i)bp(j))0

The last inequality follows from the fact that  ij and p(j)p(i) yield  aiaj  and bp(j)bp(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 i=1i=naibp(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 a1,a2,......,an, i=1i=nain(i=1i=nai)1n.

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(x1,x2,....,xn)g(x1,x2,....,xn) for which f(tx1,tx2,...txn)f(x1,x2,...,xn)=g(tx1,tx2,....,txn)g(x1,x2,...,xn)=tk 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 i=1i=nai=1. Let x1,x2,.....,xn be arbitrary positive reals such that ai=xixi+1 i<n. Then by the normalization condition, an=xnx1.

So it needs to be proven that x1x2+x2x3+......xnx1n.

Can you write n as x1x1+x2x2+....+xnxn? Do you see the rearrangement inequality hidden somewhere?

So consider a permutation p on {1,2,.....,n} such that xp(i)xp(j) for ij.

Let ai=xp(i) and bi=1xp(n+1i). Then for ij, aiaj and bibj.

So applying the first part of the rearrangement inequality on ai and bi, the lower bound on i=1i=nxixq(i) for any permutation q is i=1i=naibn+1i=i=1i=nxp(i)xp(i)=n.

So now just take q(1)=2, q(2)=3,......q(n)=1 and the proof is completed


Inequality 2: Generalized Nesbitt's inequality

Given n positive reals x1,x2,.....,xn, let s=x1+x2+......+xn. We need to prove

i=1i=nxisxinn1.

WLOG assume x1x2.......xn. Then sx1sx2.......sxn and 1sx11sx2.......1sxn. So let bi=xi and ai=1sxi

Now consider n1 permutations p1,p2,.....,pn1 such that

 pi(x)=(x+i1)(modn)+1.

By the second part of rearrangement inequality, j=1j=n1i=1i=naibpj(i)(n1)i=1i=naibi=(n1)i=1i=nxisxi

j=1j=n1i=1i=naibpj(i)=i=1i=nai(j=1j=n1bpj(i))=i=1i=n1sxi(sxi)=n.

Thus we get i=1i=nxisxinn1


Inequality 3: Chebyshev's inequality

Given 2n positive reals a1,a2,......,an and b1.b2.......,bnijaiaj and bibj. We need to prove

n(i=1i=naibi)(i=1i=nai)(i=1i=nbi)n(i=1i=naibn+1i)

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 pi(x)=(x+i1) (modn)+1. Then (i=1i=nai)(i=1i=nbi)=j=1j=ni=1i=naibpj(i)

And by Rearrangement Inequality,

ni=1i=naibn+1ij=1j=ni=1i=naibpj(i)ni=1i=naibi


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 max(a,b,c)min(a,b,c)+min(a,b,c)max(a,b,c)a+b+cabc31

Solution: WLOG let abc.  So 1c1b1a. By Chebyshev's inequality,3(ac+bb+ca)(a+b+c)(1a+1b+1c).

Now by AM-GM inequality, (a+b+c)(1a+1b+1c)3(a+b+c)abc3

Combining the above 2 inequalities and noting that a=max(a,b,c) and c=min(a,b,c), we are done

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 a1,a2,.......,an be n distinct positive integers. Prove that i=1i=naii2i=1i=n1i.

Solution: Consider a permutation p on {1,2,......,n} such that ijn, ap(i)ap(j) (basically define an ordering on ai). So ap(n)ap(n1)......ap(1) and 112122........1n2. Thus by the first part of the Rearrangement Inequality,

i=1i=naii2i=1i=nap(i)i2

Now consider the first condition of the problem statement. What can we say if ai's are distinct positive integers? ap(i)i !!

i=1i=nap(i)i2i=1i=nii2=i=1i=n1i

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 p is and what values ai take, you just need to know what matchings of ai and 1i2 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 a2+bcb+c+b2+aca+c+c2+aba+ba+b+c

Solution: Due to the symmetry present in the inequality, WLOG assume that abc.

Thus, a2b2c2 and 1b+c1a+c1a+b.

Applying part 2 of the rearrangement inequality, a2b+c+b2c+a+c2a+bb2b+c+c2c+a+a2a+b

a2+bcb+c+b2+cac+a+c2+aba+bb2+bcb+c+c2+cac+a+a2+aba+b=a+b+c

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 ab+c+bc+a+ca+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 1b+c. Another example is a2(b+c)+b2(c+a)+c2(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 a2 and b+c. In the above problem, we assumed abc, but by this we can't comment on the relative ordering of a2+bc and likewise terms. But by this we can indeed deduce the relative ordering of terms a2 and likewise and 1b+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 bcb+c,cac+a and aba+b to both sides to get the desired inequality.

Problem 4:

Let a,b and c be positive reals. Prove that a+bb+c+b+cc+a+c+aa+b(a+b+c)2ab+bc+ca

Solution: Multiplying both sides by (ab+bc+ca) and cancelling out some terms it needs to be proven that bc(a+b)b+c+ca(b+c)c+a+ab(c+a)a+bab+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)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.

  • abc

Thus 1b+1c1c+1a1a+1baba+bcac+abcb+c

Also a+bc+ab+c. Thus by second part of RI, ab(a+b)a+b+ca(c+a)c+a+bc(b+c)b+cab(c+a)a+b+ca(b+c)c+a+bc(a+b)b+c

  • acb

Thus 1b+1c1a+1b1c+1acac+aaba+bbcb+c

Also c+aa+bb+c. Thus by the second part of RI, ca(c+a)c+a+ab(a+b)a+b+bc(b+c)b+cca(b+c)c+a+ab(c+a)a+b+bc(a+b)b+c

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

Comments

Popular posts from this blog

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 wha...

Functional Equations 101

Let's get to the math:  Let there be two sets X and Y. A function  from X to Y denoted as f:XY is assigning a value in Y for every element in X. We say that X is the domain of the function f and Y is the range.  A function f:Xy is said to be injective if f(x)=f(x)x=x To put it in a more abstract way, if there is some aY then there is at most one bX such that f(b)=a holds true.  A function is said to be surjective when for any aY there is at least one bX such that f(b)=a holds true.  A function is bijective if for every aY there is exactly one bX such that f(b)=x. Bijective functions are basically functions which are both injective and surjective.  Bonus: A function f:XX is known as an involution if f(f(x))=xxX  As an exercise, the readers should try to prove that every function th...

Some Wandering Through Orthic Triangles

 Hi, I am Emon and I it's been long since I posted last. Today I will try to give you some ideas on how to work with a special type of triangle, known as " Orthic Triangles ". In this post, I will mainly focus on problem-solving, but still, let me first give you some ideas on what exactly it is and what properties does it have... Definition (Orthic Triangle). Let ABC be a triangle and let D,E,F be the foot of the perpendiculars from A,B,C to BC,CA and AB, respectively. Then, DEF is known as the orthic triangle of ABC. Lemma 1 (Orthic Triangle). If DEF is the orthic triangle of ABC with orthocenter H, then the following conditions are satisfied : (i) AEHF is a cyclic quadrilateral with circumdiameter AH. (ii) BCEF is a cyclic quadrilateral with circumdiameter BC. (iii) H is the incenter of DEF. Lemma 2. ABE=ADE and ACF=ADF. (We can prove this w...