Difference between revisions of "Rearrangement Inequality"

Revision as of 13:16, 20 June 2006

The Rearrangement Inequality states that, if $A=\{a_1,a_2,\cdots,a_n\}$ is a permutation of a set of nonnegative integers, and $B=\{b_1,b_2,\cdots,b_n\}$ is a permutation of another set of nonnegative integers, the quantity $a_1b_1+a_2b_2+\cdots+a_nb_n$ is maximized when ${A}$ and ${B}$ are similarly sorted (that is, if $a_k$ is greater than or equal to exactly ${i}$ of the other members of $A$ , then ${b_k}$ is also greater than or equal to exactly ${i}$ of the other members of $B$ ). Conversely, $a_1b_1+a_2b_2+\cdots+a_nb_n$ is minimized when $A$ and $B$ are oppositely sorted (that is, if $a_k$ is less than or equal to exactly ${i}$ of the other members of $A$ , then ${b_k}$ is also less than or equal to exactly ${i}$ of the other members $B$ ).

Introductory Problem Solving

Students who find themselve not yet ready to apply or understand the Rearrangement Inequality can read up on the greedy algorithm.

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 proper, it is useful to consider the case where $n=2$ . Without loss of generality, sort $A$ and $B$ so that $a_2 \geq a_1$ and $b_2\geq b_1$ . By hypothesis, $(a_2-a_1)(b_2-b_1) \geq 0$ . Expanding and taking some terms to the other side of the inequality, we get $a_1b_1+a_2b_2 \geq a_1b_2+a_2b_1$ , as desired.

Now for the general case. Again, without loss of generality, set $a_1 \leq a_2 \leq \cdots \leq a_n$ and $b_1 \leq b_2 \leq \cdots \leq b_n$ ; and suppose the grouping that maximizes the desired sum of products is not the one that pairs ${a_1}$ with ${b_1}$ , ${a_2}$ with ${b_2}$ , and so on. This means that there is at least one instance where ${a_i}$ is paired with $b_j$ while $a_k$ is paired with ${b_l}$ , where $i < j$ and $k > l$ . However, using the technique seen above to prove the inequality for $n=2$ , we can see that the sum of products can only increase if we instead pair ${a_i}$ with ${b_l}$ and $a_k$ with $b_j$ (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.

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.

Page

Toolbox

Search