Lemma › Guides › The rearrangement inequality in olympiad problems: when to use it
Guide

The rearrangement inequality in olympiad problems: when to use it

The rearrangement inequality is the one that says what common sense says. If you are pairing up big numbers with big numbers, the total is as large as it can get. Pair big with small and you get the smallest total. What makes it a tool is that it lets you compare a sum you are stuck on with a sum you can compute.

The statement

Let a1≤a2≤⋯≤ana_1 \le a_2 \le \cdots \le a_n and b1≤b2≤⋯≤bnb_1 \le b_2 \le \cdots \le b_n be real numbers. For every permutation σ\sigma of {1,…,n}\{1, \dots, n\},

a1bn+a2bn−1+⋯+anb1  ≤  a1bσ(1)+⋯+anbσ(n)  ≤  a1b1+a2b2+⋯+anbn.a_1 b_{n} + a_2 b_{n-1} + \cdots + a_n b_1 \;\le\; a_1 b_{\sigma(1)} + \cdots + a_n b_{\sigma(n)} \;\le\; a_1 b_1 + a_2 b_2 + \cdots + a_n b_n.

The largest sum pairs the lists in the same order. The smallest pairs them in opposite orders. If all the aia_i are equal, or all the bib_i are, every pairing gives the same sum.

The numbers do not have to be positive. Negatives are fine.

The proof

Take any arrangement that is not already sorted the same way. Then there is a pair of positions i<ji < j where ai≤aja_i \le a_j but the matched bb values are in the wrong order: bσ(i)>bσ(j)b_{\sigma(i)} > b_{\sigma(j)}. Swap the two bb values. The change in the sum is

(aibσ(j)+ajbσ(i))−(aibσ(i)+ajbσ(j))=(aj−ai)(bσ(i)−bσ(j))≥0.\big(a_i b_{\sigma(j)} + a_j b_{\sigma(i)}\big) - \big(a_i b_{\sigma(i)} + a_j b_{\sigma(j)}\big) = (a_j - a_i)(b_{\sigma(i)} - b_{\sigma(j)}) \ge 0.

So the swap never lowers the sum. Keep swapping out-of-order pairs. Each swap removes at least one inversion, so after finitely many steps you reach the sorted arrangement. That arrangement therefore has the largest sum. The smallest sum is the same argument with the second list reversed.

The signals

Example: numbers

Take the lists (1,2,5)(1, 2, 5) and (3,4,10)(3, 4, 10). Sorted together, the sum is 1⋅3+2⋅4+5⋅10=611\cdot3 + 2\cdot4 + 5\cdot10 = 61. Reversed, it is 1⋅10+2⋅4+5⋅3=331\cdot10 + 2\cdot4 + 5\cdot3 = 33. All six ways to pair them give sums between 3333 and 6161, and no other pairing reaches either end.

Example: a cubic with a cyclic sum

Prove a3+b3+c3≥a2b+b2c+c2aa^3 + b^3 + c^3 \ge a^2 b + b^2 c + c^2 a for positive reals.

The lists (a,b,c)(a, b, c) and (a2,b2,c2)(a^2, b^2, c^2) are sorted in the same way, since x↦x2x \mapsto x^2 is increasing on the positive reals. So a⋅a2+b⋅b2+c⋅c2a\cdot a^2 + b\cdot b^2 + c\cdot c^2 is the sorted pairing, and by rearrangement it is at least any other pairing. Pair aa with c2c^2, bb with a2a^2 and cc with b2b^2. That gives ac2+ba2+cb2ac^2 + ba^2 + cb^2, which is exactly the cyclic sum in the claim. Done.

Example: Nesbitt by rearrangement

For positive a,b,ca, b, c, show ab+c+bc+a+ca+b≥32\dfrac{a}{b+c} + \dfrac{b}{c+a} + \dfrac{c}{a+b} \ge \dfrac32. This is the archive's Nesbitt problem.

The sum is symmetric in a,b,ca, b, c, so you may relabel and assume a≥b≥ca \ge b \ge c. Then b+c≤c+a≤a+bb + c \le c + a \le a + b, so the reciprocals are ordered 1b+c≥1c+a≥1a+b\dfrac{1}{b+c} \ge \dfrac{1}{c+a} \ge \dfrac{1}{a+b}. The lists (a,b,c)(a, b, c) and (1b+c,1c+a,1a+b)\left(\dfrac1{b+c}, \dfrac1{c+a}, \dfrac1{a+b}\right) are sorted the same way. The sum in the problem is that sorted pairing, so it is at least each of the two shifted pairings:

S≥bb+c+cc+a+aa+b,S≥cb+c+ac+a+ba+b.S \ge \frac{b}{b+c} + \frac{c}{c+a} + \frac{a}{a+b}, \qquad S \ge \frac{c}{b+c} + \frac{a}{c+a} + \frac{b}{a+b}.

Add the two. Each denominator now appears with the numerators that add up to it, so the right side is 1+1+1=31 + 1 + 1 = 3. Then 2S≥32S \ge 3.

For the other ways of proving it, see Nesbitt's inequality: when to use it.

Example: distinct integers

Let a1,…,ana_1, \dots, a_n be distinct positive integers. Show that ∑akk2≥∑1k\displaystyle\sum \frac{a_k}{k^2} \ge \sum \frac1k.

Put the aka_k in increasing order b1<b2<⋯<bnb_1 < b_2 < \cdots < b_n. The numbers 1k2\tfrac{1}{k^2} decrease as kk grows, so the smallest pairing with them puts the bb's in increasing order. Hence ∑ak/k2≥∑bk/k2\sum a_k/k^2 \ge \sum b_k/k^2. Because the bkb_k are distinct positive integers in increasing order, b1≥1b_1 \ge 1 and each next one is at least one larger, so bk≥kb_k \ge k. So the sum is at least ∑k/k2=∑1/k\sum k/k^2 = \sum 1/k.

For n=4n = 4, the sum over every arrangement of 1,2,3,41, 2, 3, 4 is at least 1+12+13+14=25121 + \tfrac12 + \tfrac13 + \tfrac14 = \tfrac{25}{12}, and the identity arrangement attains it.

Where it goes wrong

What to do with this

When a sum of products has two lists in it, sort both and write the same-order pairing next to the sum you have. Often the two sums differ by only a permutation, and then the inequality is free. The AM-GM and Cauchy-Schwarz technique page covers the other tools that sit beside this one, and the problem archive has inequalities to practise on.

Related guides

Techniques in this guide

Competitions this guide helps with

Train it on Lemma

Every technique here is taught explicitly, in order. 128 lessons, 1237 curated problems and unlimited generated practice at six difficulties. Free to start, no card, and the paid plan opens with 3 free days.

Find your level