PlanetMath: rearrangement inequality

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (200)
Orphanage
Unclass'd
Unproven (511)
Corrections (9)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

rearrangement inequality

(Theorem)

Let $x_1,x_2,\ldots,x_n$ and $y_1,y_2,\ldots,y_n$ two sequences of positive real numbers. Then the sum

$\displaystyle x_1y_1+x_2y_2+\cdots+x_ny_n$

is maximized when the two sequences are ordered in the same way (i.e. $x_1\le x_2\le \cdots \le x_n$ and $y_1\le y_2\le\cdots\le y_n$ ) and is minimized when the two sequences are ordered in the opposite way (i.e. $x_1\le x_2\le \cdots \le x_n$ and $y_1\ge y_2\ge\cdots\ge y_n$ ).

This can be seen intuitively as: If $x_1,x_2,\ldots,x_n$ are the prices of kinds of items, and $y_1,y_2,\ldots,y_n$ the number of units sold of each, then the highest profit is when you sell more items with high prices and fewer items with low prices (same ordering), and the lowest profit happens when you sell more items with lower prices and less items with high prices (opposite orders).

"rearrangement inequality" is owned by drini. [ owner history (1) ]

(view preamble)