§ Rearrangement inequality

If a[i]a[i] is a non-decreasing sequence: a[1]a[2]a[n]a[1] \leq a[2] \leq \dots a[n], and similarly b[i]b[i] is a non-decreasing sequence: b[1]b[2]b[n]b[1] \leq b[2] \leq b[n] then we have that:
ia[i]b[i]ia[σ[i]b[i] \sum_i a[i] b[i] \geq \sum_i a[\sigma[i] b[i]
for any permutation σSn\sigma \in S_n.
insight: the greedy strategy is the best. Think of b[n]b[n] as the max. number of times we are allowed to pick some a[i]a[i]. It is best to be greedy and pick the value maxia[i]\max_i a[i] b[n]b[n] number of times. maxia[i]=a[n]\max_i a[i] = a[n]. Thus having a[n]b[n]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=ia[i]b[i]S = \sum_i a[i] b[i]. Let TT be SS with us picking the value a[r]a[r] b[s]b[s] times, and picking the value a[s]a[s] b[r]b[r] times. This gives
T=ir,sa[i]b[i]+a[r]b[s]+a[s]b[r] T = \sum_{i \neq r, s} a[i] b[i] + a[r]b[s] + a[s]b[r]
Since we wish to show S>TS > T, let's consider STS - T:
ST=ia[i]b[i](ir,sa[i]b[i]+a[r]b[s]+a[s]b[r])=ir,sa[i]b[i]+a[r]b[r]+a[s]b[s](ir,sa[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]) \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<sr < s we have b[r]b[s]b[r] \leq b[s], hence b[r]b[s]<0b[r] \leq b[s] < 0. For the product to be greater than zero, we need a[r]a[s]a[r] \leq a[s], or a[s]a[r]a[s] \geq a[r] when s>rs > 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)/2pq(p + q)/2 \geq \sqrt{pq}. Let WLOG pqp \leq q. Pick the sequences:
a=[p,q];a=[q,p];b=[p,q] a = [p, q]; a' = [q, p]; b = [p, q]
Then the rearrangement inequality gives us:
a[1]b[1]+a[2]b[2]a[1]b[1]+a[2]b[2]p2+q2qp+pq(p2+q2)/2pq \begin{aligned} &a[1]b[1] + a[2]b[2] \geq a'[1]b[1] + a'[2]b[2] \\ &p^2 + q^2 \geq qp + pq \\ &(p^2 + q^2)/2 \geq pq \end{aligned}
Pick p=r,q=sp = \sqrt{r}, q = \sqrt{s} to arrive at:
(r+s)/2rs (r + s)/2 \geq \sqrt{rs}
and thus we are done.

§ References

  • Inequalities: a mathematical olympiad approach