A Universe of Sorts

§ Rearrangement inequality

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:

\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

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} &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 = \sqrt{r}, q = \sqrt{s}

to arrive at:

(r + s)/2 \geq \sqrt{rs}

and thus we are done.

§ References

Inequalities: a mathematical olympiad approach