Inequalities Revisited. Topic: Inequalities. Level: Olympiad.

Theorem: (Rearrangement Inequality) Given two nondecreasing sequences of positive reals $x_1 \le x_2 \le \cdots \le x_n$ and $y_1 \le y_2 \le \cdots \le y_n$,

$ \displaystyle \sum_{i=1}^n x_iy_i \ge \sum_{i=1}^n x_iy_{\delta(i)} $,

where $ \delta $ is some permutation of $1,2, \ldots, n $.

--------------------

Comment: The Rearragement Inequality is extremely useful, and can quickly kill some inequalities that may be a hassle to AM-GM over and over again, as you'll see in the next example. The proof of the theorem simply requires considering a possible permutation, subtracting it away from the maximum, and showing that the difference is greater than zero.

--------------------

Problem: (1999 United Kingdom - #7) Given three non-negative reals $p,q,r$ such that $p+q+r = 1$, prove that

$ 7(pq+qr+rp) \le 2+9pqr $.

Solution: We notice that the inequality we wish to prove is not homogenous - that is, the sums of the powers on the terms are not equal. Most of the classical inequalities require you to homogenize, and given our condition, we can do so (by multiplying by $p+q+r$ when necessary). After homogenizing, the inequality becomes

$ 7(pq+qr+rp)(p+q+r) \le 2(p+q+r)^3+9pqr $.

Now this may look uglier than before, but we notice a lot of terms cancel, leaving (you may do the algebra yourself if you wish)

$ p^2q+p^2r+q^2r+q^2p+r^2p+r^2q \le 2(p^3+q^3+r^3) $.

With enough experience, this will be an obvious direct result of Rearrangement, but to explicitly use it, we set (applied three times with $n = 2$ and WLOG assuming $p \le q \le r$):

$ x_1 = p^2 \le x_2 = q^2 $
$ y_1 = p \le y_2 = q $, from which we have

$ \displaystyle \sum_{i=1}^2 x_iy_i = p^3+q^3 \ge \sum_{i=1}^2 x_iy_{\delta(i)} = p^2q+q^2p $

where $ \delta = 2,1 $. As you can see applying this on the pairs $ (p,r); (q,r) $ the same way and summing them up, we get the desired result

$ p^2q+p^2r+q^2r+q^2p+r^2p+r^2q \le 2(p^3+q^3+r^3) $.

QED.

--------------------

Comment: An "extension" of the Rearrangement Inequality, is the Muirhead Inequality, which effectively demolishes symmetric, homogenized inequalities.


--------------------


Practice Problem #1: Prove, using Rearrangement, the Trivial Inequality:

$ (x-y)^2 \ge 0 $

for positive reals $x,y$.

Practice Problem #2: Prove, using Rearrangement, a special case of the Power-Mean Inequality:

$ \sqrt[n]{\frac{x^n+y^n+z^n}{3}} \ge \frac{x+y+z}{3} $

for a positive integer $n$ and positive reals $x,y,z$.

Practice Problem #3: Given positive reals $ a,b,c $, prove that

$ \frac{a}{b+c} + \frac{b}{a+c} + \frac{c}{a+b} \ge \frac{a}{a+b} + \frac{b}{b+c} + \frac{c}{c+a} $.