§ Rearrangement inequality
If is a non-decreasing sequence: , and
similarly is a non-decreasing sequence: then
we have that:
for any permutation .
insight: the greedy strategy is the best. Think of as the max. number of times we are allowed to pick some . It is best to be greedy and pick the value number of times. . Thus having will beat all others.
The proof strategy is to: show what happens for a transposition. Every
permutation can be broken down into transpositions and thus we are done.
Let . Let be with us picking the value times,
and picking the value times. This gives
Since we wish to show , let's consider :
Since we have , hence . For the product
to be greater than zero, we need , or when .
Hence, for a transposition, we are done. Thus we are immediately done
for any permutation:
§ Application: AM-GM
Say we wish to show . Let WLOG .
Pick the sequences:
Then the rearrangement inequality gives us:
Pick to arrive at:
and thus we are done.
- Inequalities: a mathematical olympiad approach