Difference between revisions of "Rearrangement Inequality"
m (proofreading) |
(The rearrangement inequality does not require that its terms have a specific sign, or that they be integers.) |
||
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 | + | The '''Rearrangement Inequality''' states that, if <math>A=\{a_1,a_2,\cdots,a_n\}</math> is a permutation of a finite set of real numbers, and <math>B=\{b_1,b_2,\cdots,b_n\}</math> is a permutation of another finite set of real numbers, 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>). |
Line 16: | Line 16: | ||
== 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]]. It is particularly useful in that it does not require any terms of either sequence to be positive or negative, unlike the [[Power mean inequality|power-mean]] family of inequalities. |
Revision as of 13:50, 28 June 2006
The Rearrangement Inequality states that, if is a permutation of a finite set 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 less than or equal to exactly of the other members ).
Contents
[hide]Introductory Problem Solving
Students who find themselves 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. 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.