If $a[i]$ is a non-decreasing sequence: $a[1] \leq a[2] \leq \dots a[n]$, and similarly $b[i]$ is a non-decreasing sequence: $b[1] \leq b[2] \leq b[n]$ then we have that:

for any permutation $\sigma \in S_n$.

insight: the greedy strategy is the best. Think of $b[n]$ as the max. number of times we are allowed to pick some $a[i]$. It is best to be greedy and pick the value $\max_i a[i]$ $b[n]$ number of times. $\max_i a[i] = a[n]$. Thus having $a[n]b[n]$ will beat all others.

§ Proof

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 $S = \sum_i a[i] b[i]$. Let $T$ be $S$ with us picking the value $a[r]$ $b[s]$ times, and picking the value $a[s]$ $b[r]$ times. This gives

Since we wish to show $S > T$, let's consider $S - T$:

Since $r < s$ we have $b[r] \leq b[s]$, hence $b[r] \leq b[s] < 0$. For the product to be greater than zero, we need $a[r] \leq a[s]$, or $a[s] \geq a[r]$ when $s > r$.

Hence, for a transposition, we are done. Thus we are immediately done for any permutation:

§ Application: AM-GM

Say we wish to show $(p + q)/2 \geq \sqrt{pq}$. Let WLOG $p \leq q$. Pick the sequences:

Then the rearrangement inequality gives us:

Pick $p = \sqrt{r}, q = \sqrt{s}$ to arrive at:

and thus we are done.

§ References

• Inequalities: a mathematical olympiad approach