Rearrangement Inequality
The Rearrangement Inequality states that, if is a permutation of a finite set (in fact, multiset) of real numbers and is a permutation of another finite set of real numbers, the quantity is maximized when and are similarly sorted (that is, if is greater than or equal to exactly of the other members of , then is also greater than or equal to exactly of the other members of ). Conversely, is minimized when and are oppositely sorted (that is, if is less than or equal to exactly of the other members of , then is also greater than or equal to exactly of the other members ).
Contents
[hide]Introductory
Consider the following simple application: suppose you are involved in the hold-up of a convenience store. You note, as you are emptying the register, that there are different numbers of each denomination (penny, nickel, dime, quarter, dollar bill, five dollar bill, ten dollar bill and twenty dollar bill) in the register. When would your take be maximized? Certainly, you would hope that there would be the largest number of twenty dollar bills, then the next largest number of tens, etc. Meanwhile, you would find yourself very disappointed if there were more pennies than nickels, more nickels than dimes, and so on. This is a simple application of the rearrangement inequality. It is also an application of the greedy algorithm, so one possible interpretation of the rearrangement inequality is that sometimes, the greedy algorithm works.
Intermediate
Proof of the Rearrangement Inequality
The proof of the Rearrangment Inequality can be handled with proof by contradiction. Only the maximization form is proved here; the minimization proof is virtually identical.
Before we begin the proof properly, it is useful to consider the case where . Without loss of generality, sort and so that and . By hypothesis, . Expanding and taking some terms to the other side of the inequality, we get , as desired.
Now for the general case. Again, without loss of generality, set and ; and suppose the grouping that maximizes the desired sum of products is not the one that pairs with , with , and so on. This means that there is at least one instance where is paired with while is paired with , where and . However, using the technique seen above to prove the inequality for , we can see that the sum of products can only increase if we instead pair with and with (unless both a's or both b's are equal, in which case either we can choose another pair of products or note that the current arrangement is actually identical to the desired one), which contradicts our assumption that the arrangement we had was already the largest one.
Note: The minimization equality can be very easily proved by noting that if we have the set , ordered in decreasing order and the set , ordered in increasing order, then the maximum sum is just . Thus, by negating all values the inequality follows.
Uses
The Rearrangement Inequality has a wide range of uses, from MathCounts level optimization problems to Olympiad level inequality problems. A relatively simple example of its use in solving higher-level problems is found in the proof of Chebyshev's Inequality. It is particularly useful in that it does not require any terms of either sequence to be positive or negative, unlike the power-mean family of inequalities.