1979 USAMO Problems/Problem 3
is an arbitrary sequence of positive integers. A member of the sequence is picked at random. Its value is . Another member is picked at random, independently of the first. Its value is . Then a third value, . Show that the probability that is divisible by is at least .
The given problem is equivalent to proving that .
Try proving this inequality for all nonnegative real numbers x, y, z; not just positive integers.
Let x equal the probability of picking an element of the sequence equivalent to 0 mod 3, y equal those 1 mod 3, and z equal those 2 mod 3. Then, considering that 0+0+0, 1+1+1, 2+2+2, and 0+1+2 are divisible by 3, we obtain the equivalent inequality in the First Hint. This simplifies to Now, we attempt to prove that for all nonnegative real numbers x, y, z; our inequality will follow from this. But this is just Schur's Inequality with r = 1! This completes the proof.
Note: Schur's Inequality states that . This can be proven by setting WLOG and bunching together terms that are nonnegative. Challenge: when does equality hold? When does equality hold in the problem?
|1979 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5|
|All USAMO Problems and Solutions|