Difference between revisions of "Rearrangement Inequality"
m (Rearrangement inequality moved to Rearrangement Inequality over redirect: revert) |
Mathboy100 (talk | contribs) |
||
(4 intermediate revisions by 4 users not shown) | |||
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 [[finite]] [[set]] (in fact, [[multiset]]) of [[real number]]s 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 | + | The '''Rearrangement Inequality''' states that, if <math>A=\{a_1,a_2,\cdots,a_n\}</math> is a [[permutation]] of a [[finite]] [[set]] (in fact, [[multiset]]) of [[real number]]s 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 greater than or equal to exactly <math>{i}</math> of the other members <math>B</math>). |
Line 10: | Line 10: | ||
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. | ||
− | Before we begin the proof | + | Before we begin the proof properly, it is useful to consider the case where <math>n=2</math>. Without loss of generality, sort <math>A</math> and <math>B</math> so that <math>a_2 \geq a_1</math> and <math>b_2\geq b_1</math>. By hypothesis, <math>(a_2-a_1)(b_2-b_1) \geq 0</math>. Expanding and taking some terms to the other side of the inequality, we get <math>a_1b_1+a_2b_2 \geq a_1b_2+a_2b_1</math>, as desired. |
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. | ||
+ | Note: The minimization equality can be very easily proved by noting that if we have the set <math>\{-b_1, -b_2, \ldots\}</math>, ordered in decreasing order and the set <math>\{a_1, a_2, \ldots\}</math>, ordered in increasing order, then the maximum sum is just <math>-a_1b_k - a_2b_{k-1} + \ldots</math>. Thus, by negating all values the inequality follows. | ||
== Uses == | == Uses == | ||
Line 23: | Line 24: | ||
==External Links== | ==External Links== | ||
− | *[ | + | *[https://www.math.ualberta.ca/pi/issue2/page21-23.pdf The Rearrangement Inequality by Dragos Hrimiuc] |
− | [[Category: | + | |
− | [[Category: | + | [[Category:Algebra]] |
+ | [[Category:Inequalities]] |
Latest revision as of 12:54, 26 January 2023
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.