In mathematics, the rearrangement inequality states that for every choice of real numbers and every permutation of If the numbers are different, meaning that then the lower bound is attained only for the permutation which reverses the order, that is, for all and the upper bound is attained only for the identity, that is, for all Note that the rearrangement inequality makes no assumptions on the signs of the real numbers. Applications Many important inequalities can be proved by the rearrangement inequality, such as the arithmetic mean – geometric mean inequality, the Cauchy–Schwarz inequality, and Chebyshev's sum inequality. One particular consequence is that if then (by using ): holds for every permutation of Intuition The rearrangement inequality is actually very intuitive. Imagine there is a heap of $10 bills, a heap of $20 bills and one more heap of $100 bills. You are allowed to take 7 bills from a heap of your choice and then the heap disappears. In the second round you are allowed to take 5 bills from another heap and the heap disappears. In the last round you may take 3 bills from the last heap. In what order do you want to choose the heaps to maximize your profit? Obviously, the best you can do is to gain dollars. This is exactly what rearrangement inequality says for sequences and It is also an application of a greedy algorithm. Proof The lower bound follows by applying the upper bound to Therefore, it suffices to prove the upper bound. Since there are only finitely many permutations, there exists at least one for which is maximal. In case there are several permutations with this property, let σ denote one with the highest number of fixed points. We will now prove by contradiction, that σ has to be the identity (then we are done). Assume that σ is the identity. Then there exists a j in {1, ..., n − 1} such that σ(j) ≠ j and σ(i) = i for all i in {1, ..., j − 1}. Hence σ(j) > j and there exists a k in {j + 1, ..., n} with σ(k) = j. Now Therefore, Expanding this product and rearranging gives hence the permutation which arises from σ by exchanging the values σ(j) and σ(k), has at least one additional fixed point compared to σ, namely at j, and also attains the maximum. This