1979 USAMO Problems/Problem 3
Problem
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 .
First Hint
The given problem is equivalent to proving that .
Second Hint
Try proving this inequality for all nonnegative real numbers x, y, z; not just positive integers.
Final Hint
Prove that
Solution
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?
See Also
1979 USAMO (Problems • Resources) | ||
Preceded by Problem 2 |
Followed by Problem 4 | |
1 • 2 • 3 • 4 • 5 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.