Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Rearrangement Inequality"

m (Rearrangement Inequality moved to Rearrangement inequality: Changing capitalization)
 
(13 intermediate revisions by 9 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 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 [[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>).
  
  
−
== Introductory Problem Solving ==
+
== Introductory ==
−
Students who find themselve not yet ready to apply or understand the Rearrangement Inequality can read up on the [[greedy algorithm]].
+
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.
  
  
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 proper, 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.
+
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 ==
−
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]] 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 [[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.
 +
 
 +
==See Also==
 +
*[[Chebyshev's Inequality]]
 +
*[[Power Mean Inequality]]
 +
 
 +
==External Links==
 +
*[https://www.math.ualberta.ca/pi/issue2/page21-23.pdf The Rearrangement Inequality by Dragos Hrimiuc]
 +
 
 +
[[Category:Algebra]]
 +
[[Category:Inequalities]]

Latest revision as of 12:54, 26 January 2023

The Rearrangement Inequality states that, if $A=\{a_1,a_2,\cdots,a_n\}$ is a permutation of a finite set (in fact, multiset) of real numbers and $B=\{b_1,b_2,\cdots,b_n\}$ is a permutation of another finite set of real numbers, 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 greater than or equal to exactly ${i}$ of the other members $B$).


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 $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.

Note: The minimization equality can be very easily proved by noting that if we have the set $\{-b_1, -b_2, \ldots\}$, ordered in decreasing order and the set $\{a_1, a_2, \ldots\}$, ordered in increasing order, then the maximum sum is just $-a_1b_k - a_2b_{k-1} + \ldots$. 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.

See Also

External Links

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Rearrangement_Inequality&oldid=188066"