IMO 2003 SL A6

Origin: USA | Category: Algebra

Problem

Let n be a positive integer and let (x1, . . . , xn), (y1, . . . , yn) be two sequences of positive real numbers. Suppose (z2, z3, . . . , z2n) is a sequence of positive real numbers such that z2 i+j \geqxiyj for all 1 \leqi, j \leqn. Let M = max{z2, . . . , z2n}. Prove that M + z2 + \cdot \cdot \cdot + z2n 2n 2 \geq x1 + \cdot \cdot \cdot + xn n  y1 + \cdot \cdot \cdot + yn n  .

Solution

Set X = max{x1, . . . , xn} and Y = max{y1, . . . , yn}. By replacing xi by x′ i = xi X , yi by y′ i = yi Y and zi by z′ i = zi \sqrt XY , we may assume that X = Y = 1. It is sufficient to prove that M + z2 + \cdot \cdot \cdot + z2n \geqx1 + \cdot \cdot \cdot + xn + y1 + \cdot \cdot \cdot + yn, (1) because this implies the result by the A-G mean inequality. To prove (1) it is enough to prove that for any r, the number of terms greater than r on the left-hand side of (1) is at least that number on the right-hand side of (1). If r \geq1, then there are no terms on the right-hand side greater than r. Suppose that r < 1 and consider the sets A = {i | 1 \leqi \leqn, xi > r} and B = {i | 1 \leqi \leqn, yi > r}. Set a = |A| and b = |B|. If xi > r and yj > r, then zi+j \geq\sqrtxiyj > r; hence C = {k | 2 \leqk \leq2n, zk > r} ⊇A + B = {\alpha + \beta | \alpha \inA, \beta \inB}. It is easy to verify that |A+B| \geq|A|+|B|−1. It follows that the number of zk’s greater than r is \geqa + b −1. But in that case M > r, implying that at least a + b elements of the left-hand side of (1) is greater than r, which completes the proof.