# 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 |