Difference between revisions of "Rearrangement Inequality"
(A brief description of the Rearrangement Inequality) |
(wrote intro section and reorganized a bit) |
||
Line 1: | Line 1: | ||
The '''Rearrangement Inequality''' states that, if <math>A=\{a_1,a_2,\cdots,a_n\}</math> is a permutation of a set of nonnegative integers, and <math>B=\{b_1,b_2,\cdots,b_n\}</math> is a permutation of another set of nonnegative integers, the quantity <math>a_1b_1+a_2b_2+\cdots+a_nb_n</math> is maximized when <math>{A}</math> and <math>{B} </math> are similarly sorted (that is, if <math>a_k</math> is greater than or equal to exactly <math>{i}</math> of the other members of <math>A</math>, then <math> {b_k} </math> is also greater than or equal to exactly <math>{i}</math> of the other members of <math>B</math>). Conversely, <math>a_1b_1+a_2b_2+\cdots+a_nb_n</math> is minimized when <math>A</math> and <math>B</math> are oppositely sorted (that is, if <math>a_k</math> is less than or equal to exactly <math>{i}</math> of the other members of <math>A</math>, then <math>{b_k}</math> is also less than or equal to exactly <math>{i}</math> of the other members <math>B</math>). | The '''Rearrangement Inequality''' states that, if <math>A=\{a_1,a_2,\cdots,a_n\}</math> is a permutation of a set of nonnegative integers, and <math>B=\{b_1,b_2,\cdots,b_n\}</math> is a permutation of another set of nonnegative integers, the quantity <math>a_1b_1+a_2b_2+\cdots+a_nb_n</math> is maximized when <math>{A}</math> and <math>{B} </math> are similarly sorted (that is, if <math>a_k</math> is greater than or equal to exactly <math>{i}</math> of the other members of <math>A</math>, then <math> {b_k} </math> is also greater than or equal to exactly <math>{i}</math> of the other members of <math>B</math>). Conversely, <math>a_1b_1+a_2b_2+\cdots+a_nb_n</math> is minimized when <math>A</math> and <math>B</math> are oppositely sorted (that is, if <math>a_k</math> is less than or equal to exactly <math>{i}</math> of the other members of <math>A</math>, then <math>{b_k}</math> is also less than or equal to exactly <math>{i}</math> of the other members <math>B</math>). | ||
− | ==Proof== | + | |
+ | == 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 | proof by contradiction]]. Only the maximization form is proved here; the minimization proof is virtually identical. | The proof of the Rearrangment Inequality can be handled with [[Proof by contradiction | proof by contradiction]]. Only the maximization form is proved here; the minimization proof is virtually identical. | ||
Line 8: | Line 14: | ||
Now for the general case. Again, without loss of generality, set <math>a_1 \leq a_2 \leq \cdots \leq a_n</math> and <math>b_1 \leq b_2 \leq \cdots \leq b_n</math>; and suppose the grouping that maximizes the desired sum of products is not the one that pairs <math>{a_1}</math> with <math>{b_1}</math>, <math>{a_2}</math> with <math>{b_2}</math>, and so on. This means that there is at least one instance where <math>{a_i}</math> is paired with <math>b_j</math> while <math>a_k</math> is paired with <math>{b_l}</math>, where <math>i < j</math> and <math>k > l</math>. However, using the technique seen above to prove the inequality for <math>n=2</math>, we can see that the sum of products can only increase if we instead pair <math>{a_i}</math> with <math>{b_l}</math> and <math>a_k</math> with <math>b_j</math> (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. | Now for the general case. Again, without loss of generality, set <math>a_1 \leq a_2 \leq \cdots \leq a_n</math> and <math>b_1 \leq b_2 \leq \cdots \leq b_n</math>; and suppose the grouping that maximizes the desired sum of products is not the one that pairs <math>{a_1}</math> with <math>{b_1}</math>, <math>{a_2}</math> with <math>{b_2}</math>, and so on. This means that there is at least one instance where <math>{a_i}</math> is paired with <math>b_j</math> while <math>a_k</math> is paired with <math>{b_l}</math>, where <math>i < j</math> and <math>k > l</math>. However, using the technique seen above to prove the inequality for <math>n=2</math>, we can see that the sum of products can only increase if we instead pair <math>{a_i}</math> with <math>{b_l}</math> and <math>a_k</math> with <math>b_j</math> (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== | + | |
+ | == Uses == | ||
The Rearrangement Inequality has a wide range of uses, from [[MathCounts]] level [[Optimization | optimization]] problems to Olympiad level [[Inequalities | inequality]] problems. A relatively simple example of its use in solving higher-level problems is found in the proof of [[Chebyshevs inequality | Chebyshev's Inequality]]. | The Rearrangement Inequality has a wide range of uses, from [[MathCounts]] level [[Optimization | optimization]] problems to Olympiad level [[Inequalities | inequality]] problems. A relatively simple example of its use in solving higher-level problems is found in the proof of [[Chebyshevs inequality | Chebyshev's Inequality]]. |
Revision as of 00:23, 20 June 2006
The Rearrangement Inequality states that, if is a permutation of a set of nonnegative integers, and is a permutation of another set of nonnegative integers, 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 less than or equal to exactly of the other members ).
Contents
[hide]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 . 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.
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.