Difference between revisions of "Rearrangement Inequality"
Mentalgenius (talk | contribs) m (→Proof of the Rearrangement Inequality) |
Mathboy100 (talk | contribs) |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Line 13: | Line 13: | ||
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 22: | 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
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.
