## § Rearrangement inequality

If $a[i]$ is a non-decreasing sequence: $a \leq a \leq \dots a[n]$, and similarly $b[i]$ is a non-decreasing sequence: $b \leq b \leq b[n]$ then we have that:
$\sum_i a[i] b[i] \geq \sum_i a[\sigma[i] b[i]$
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
$T = \sum_{i \neq r, s} a[i] b[i] + a[r]b[s] + a[s]b[r]$
Since we wish to show $S > T$, let's consider $S - T$:
\begin{aligned} &S - T = \sum_i a[i]b[i] - (\sum_{i \neq r, s} a[i]b[i] + a[r]b[s] + a[s]b[r]) \\ &=\sum_{i \neq r, s} a[i]b[i] + a[r]b[r] + a[s]b[s] - (\sum_{i \neq r, s} a[i]b[i] + a[r]b[s] + a[s]b[r]) \\ &= a[r]b[r] + a[s]b[s] - a[r]b[s] - a[s]b[r] \\ &= a[r](b[r] - b[s]) + a[s](b[s] - b[r]) \\ &= a[r](b[r] - b[s]) - a[s](b[r] - b[s]) \\ &= (a[r] - a[s])(b[r] - b[s]) \end{aligned}
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:
$a = [p, q]; a' = [q, p]; b = [p, q]$
Then the rearrangement inequality gives us:
\begin{aligned} &ab + ab \geq a'b + a'b \\ &p^2 + q^2 \geq qp + pq \\ &(p^2 + q^2)/2 \geq pq \end{aligned}
Pick $p = \sqrt{r}, q = \sqrt{s}$ to arrive at:
$(r + s)/2 \geq \sqrt{rs}$
and thus we are done.