Rearrangement Inequality is the habit of ordering two sequences to extremize the paired sum $\sum a_i b_{\sigma(i)}$. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.
The sum of pairwise products of two sequences is largest when both are sorted the same way and smallest when sorted in opposite orders.
Why It Works
1
Take two pairs and compare matching the larger values together versus crossing them: $a_1 b_1 + a_2 b_2 - (a_1 b_2 + a_2 b_1) = (a_2 - a_1)(b_2 - b_1)$.
2
If $a_1 \le a_2$ and $b_1 \le b_2$, that difference $(a_2 - a_1)(b_2 - b_1) \ge 0$, so keeping the like-sorted pairing never decreases the sum.
3
Any permutation can be turned into the sorted pairing by a sequence of such adjacent swaps, each of which only increases (or holds) the sum — so the sorted-same-order pairing is the maximum.
4
Reversing the argument (pairing largest with smallest) gives the minimum; the reversed-order sum is the lower bound.
Worked Examples
Example 1
The numbers $1, 2, 3$ are to be assigned to the variables $x, y, z$ (each used once). Maximize $S = 5x + 3y + z$.
1
The fixed coefficients sorted ascending are $(1, 3, 5)$ and the values to place are $(1, 2, 3)$.
2
By the rearrangement inequality, $S$ is maximized by pairing both sequences in the same order: assign the largest value to the largest coefficient.
Prove that for all reals $a, b, c$, $a^2 + b^2 + c^2 \ge ab + bc + ca$.
1
Take the two identical sequences $(a, b, c)$ and $(a, b, c)$. Whatever their order, sorting both the same way gives the maximal pairing $a\cdot a + b\cdot b + c\cdot c = a^2 + b^2 + c^2$.
2
The pairing $a\cdot b + b\cdot c + c\cdot a$ matches each term with a permuted partner, so by rearrangement it is $\le$ the like-sorted sum.
3
Hence $a^2 + b^2 + c^2 \ge ab + bc + ca$, with equality iff $a = b = c$. (Equivalently, $\tfrac{1}{2}\sum (a-b)^2 \ge 0$.)
Answer:
$a^2 + b^2 + c^2 \ge ab + bc + ca$, equality iff $a = b = c$.
Assume WLOG $a \ge b \ge c$. Then $b + c \le c + a \le a + b$, so the reciprocals satisfy $\frac{1}{b+c} \ge \frac{1}{c+a} \ge \frac{1}{a+b}$ — the sequences $(a, b, c)$ and $\left(\frac{1}{b+c}, \frac{1}{c+a}, \frac{1}{a+b}\right)$ are sorted the same way, so $S = \sum\frac{a}{b+c}$ is the maximal (sorted) pairing.
2
By rearrangement, $S$ dominates the two cyclic shifts: $S \ge \frac{b}{b+c} + \frac{c}{c+a} + \frac{a}{a+b}$ and $S \ge \frac{c}{b+c} + \frac{a}{c+a} + \frac{b}{a+b}$.
3
Add those two lower bounds; grouping by denominator gives $\frac{b+c}{b+c} + \frac{c+a}{c+a} + \frac{a+b}{a+b} = 3$. So $2S \ge 3$, hence $S \ge \frac{3}{2}$, with equality when $a = b = c$.
Generalization: applied to a sequence and itself it yields Chebyshev's sum inequality $\frac{1}{n}\sum a_i b_i \ge \left(\frac{1}{n}\sum a_i\right)\left(\frac{1}{n}\sum b_i\right)$ for similarly-sorted sequences, and it underlies SOS / smoothing arguments in symmetric inequalities.
Where it appears: assignment-optimization problems (match big with big), and as a slick one-line proof of Nesbitt, AM-GM-style symmetric inequalities, and Cauchy-Schwarz consequences on olympiads.
Pitfall: the inequality compares the SAME multiset paired in different orders — it does not let you replace a value by a different number, only permute the pairing. And the direction depends on BOTH sequences being sorted the same way; if one is increasing and the other decreasing, the sorted-same bound is the MINIMUM, not the maximum.
Spot the Signal
Use it when you must bound a sum of paired products and you control the pairing.
You can describe the hard part as ordering two sequences to extremize the paired sum $\sum a_i b_{\sigma(i)}$, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.
Learn the Move
Start by sorting both sequences the same way for the maximum, or oppositely for the minimum.
Name the relation that makes Rearrangement Inequality legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.
Avoid These Traps
Applying it when the sequences aren't both sorted, or ignoring the sign of the terms.
Applying Rearrangement Inequality because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.
MathGrit Coach Note
Same order for the max, opposite order for the min.
Try it on:
Bound a sum of products by choosing the optimal pairing in a contest problem.