rearrangement inequality

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

$$x_1{y}_1+x_2{y}_2+\mathrm{\cdots }+x_n{y}_n$$

is maximized when the two sequences are ordered in the same way (i.e. $x_1\le x_2\le \mathrm{\cdots }\le x_n$ and $y_1\le y_2\le \mathrm{\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 \mathrm{\cdots }\le x_n$ and $y_1\ge y_2\ge \mathrm{\cdots }\ge y_n$).

This can be seen intuitively as: If $x_1,x_2,\mathrm{\dots },x_n$ are the prices of $n$ kinds of items, and $y_1,y_2,\mathrm{\dots },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
Canonical name	RearrangementInequality
Date of creation	2013-03-22 11:47:32
Last modified on	2013-03-22 11:47:32
Owner	drini (3)
Last modified by	drini (3)
Numerical id	9
Author	drini (3)
Entry type	Theorem
Classification	msc 26D15
Classification	msc 20L05
Classification	msc 22A22
Related topic	ChebyshevsInequality