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 and be real numbers. For every permutation of ,
The largest sum pairs the lists in the same order. The smallest pairs them in opposite orders. If all the are equal, or all the 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 where but the matched values are in the wrong order: . Swap the two values. The change in the sum is
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
- A sum of products of two lists, and you are free to reorder one list. The statement uses exactly this freedom.
- A cyclic sum such as that you want to compare with a symmetric sum such as . Pair with in another order and you get the cyclic sum, which is at most .
- A sum of fractions where larger numerators go with larger fractions. If forces , the two lists are sorted the same way automatically.
- A statement about "any permutation" or "distinct positive integers", where you can sort and compare.
- A problem where AM-GM is nearly right but loses information about which variable is bigger.
Example: numbers
Take the lists and . Sorted together, the sum is . Reversed, it is . All six ways to pair them give sums between and , and no other pairing reaches either end.
Example: a cubic with a cyclic sum
Prove for positive reals.
The lists and are sorted in the same way, since is increasing on the positive reals. So is the sorted pairing, and by rearrangement it is at least any other pairing. Pair with , with and with . That gives , which is exactly the cyclic sum in the claim. Done.
Example: Nesbitt by rearrangement
For positive , show . This is the archive's Nesbitt problem.
The sum is symmetric in , so you may relabel and assume . Then , so the reciprocals are ordered . The lists and 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:
Add the two. Each denominator now appears with the numerators that add up to it, so the right side is . Then .
For the other ways of proving it, see Nesbitt's inequality: when to use it.
Example: distinct integers
Let be distinct positive integers. Show that .
Put the in increasing order . The numbers decrease as grows, so the smallest pairing with them puts the 's in increasing order. Hence . Because the are distinct positive integers in increasing order, and each next one is at least one larger, so . So the sum is at least .
For , the sum over every arrangement of is at least , and the identity arrangement attains it.
Where it goes wrong
- Having the lists sorted the wrong way round. For a lower bound you want the opposite order. For an upper bound you want the same order. Write which one you are proving before you start.
- Claiming two lists are similarly sorted when they are not. In Nesbitt it is the relation between and that gives the same order. You have to check it, not assume it.
- Applying it to cyclic sums while forgetting the other cyclic direction. Both directions are rearrangements, so the same bound works for .
- Sorting one list without sorting the other. The theorem needs both lists in order before the pairing is compared.
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
- Titu's lemma: the statement, the proof, and where to use itTitu's lemma bounds a sum of fractions with squares on top by one fraction. The proof, the form that Nesbitt and IMO 1995 problem 2 reduce to, and the traps.
- How to prove an olympiad inequality, step by stepMost failed inequality proofs pick a tool in the first minute. The order of attack that picks it last: equality case, degree, substitution, shape, audit.
- Nesbitt's inequality: three proofs and how to spot it in disguiseNesbitt's inequality takes two lines to prove once you know it. The skill is seeing it inside a harder problem, and choosing which of three proofs to use.
- Jensen's inequality: how to set one up on a competition problemJensen is one line of theory and three lines of setup, and the setup is where it goes wrong. The shape that calls for it, and the two checks that save you.
- AM–GM or Cauchy–Schwarz: how to know which one to useThe two inequalities solve different shapes, not different difficulties. A shape test that picks one in seconds, and the equality case that settles the ties.
Techniques in this guide
- Classical InequalitiesEquality tells you where to aim.
Competitions this guide helps with
- AMC 1025 multiple-choice questions · 75 minutes
- AMC 1225 multiple-choice questions · 75 minutes
- MATHCOUNTSfour rounds: Sprint (30 problems), Target (8 problems in four pairs), Team (10 problems) and the oral Countdown · Sprint 40 minutes; Target 6 minutes a pair; Team 20 minutes
- Pascal, Cayley and Fermat25 questions: multiple choice in Parts A and B, and a whole number from 0 to 99 in Part C · 60 minutes
- Euclid10 questions, a mix of answer-only and full-solution parts · 2.5 hours
- COMC12 questions in three parts: four short answers, four longer answers and four full solutions · 2.5 hours
- UKMT Intermediate Challenge25 multiple-choice questions · 60 minutes
- UKMT Senior Challenge25 questions: 22 multiple choice and, as a trial from 2026, three with a three-digit answer from 000 to 999 · 90 minutes
- BMO Round 1six problems needing full written solutions, the first intended to be more accessible than the rest · 3.5 hours
- Australian Mathematics Competition30 questions: 25 multiple choice, then 5 with a whole-number answer · 75 minutes for the secondary divisions, 60 for primary
- SMO JuniorRound 1: multiple-choice and short-answer questions of equal weight. Round 2: full written solutions · 2.5 hours for Round 1, 3 hours for Round 2
- SMO SeniorRound 1: multiple-choice and short-answer questions of equal weight. Round 2: full written solutions · 2.5 hours for Round 1, 4 hours for Round 2
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