# rearrangement inequality

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

 $x_{1}y_{1}+x_{2}y_{2}+\cdots+x_{n}y_{n}$

is maximized when the two sequences are ordered in the same way (i.e. $x_{1}\leq x_{2}\leq\cdots\leq x_{n}$ and $y_{1}\leq y_{2}\leq\cdots\leq y_{n}$) and is minimized when the two sequences are ordered in the opposite way (i.e. $x_{1}\leq x_{2}\leq\cdots\leq x_{n}$ and $y_{1}\geq y_{2}\geq\cdots\geq y_{n}$).

This can be seen intuitively as: If $x_{1},x_{2},\ldots,x_{n}$ are the prices of $n$ 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).

Title rearrangement inequality RearrangementInequality 2013-03-22 11:47:32 2013-03-22 11:47:32 drini (3) drini (3) 9 drini (3) Theorem msc 26D15 msc 20L05 msc 22A22 ChebyshevsInequality