Skip to main content.

Hint to puzzle 59: Triangle inequality

Use the rearrangement inequality, stated below, to prove the left side of the inequality.

Let a1 less than or equal to a2 less than or equal to ... less than or equal to an and b1 less than or equal to b2 less than or equal to ... less than or equal to bn be real numbers.  For any permutation (c1, c2, ... cn) of (b1, b2, ... bn), we have:

a1b1 + a2b2 + ... + anbn  greater than or equal to  a1c1 + a2c2 + ... + ancn  greater than or equal to  a1bn + a2bn−1 + ... + anb1,

with equality if, and only if, (c1, c2, ... cn) is equal to (b1, b2, ... bn) or (bn, bn−1, ... b1), respectively.

That is, the sum is maximal when the two sequences, {ai} and {bi}, are sorted in the same way, and is minimal when they are sorted oppositely.

The right side of the inequality may be proved using the fact that in any triangle with sides a, b, c,  a + b > c.