Difference between revisions of "1979 USAMO Problems/Problem 3"
(→Solution) |
(→Solution) |
||
Line 19: | Line 19: | ||
''Note: Schur's Inequality states that <math>x^r(x-y)(x-z) + y^r(y-z)(y-x) + z^r(z-x)(z-y) \ge 0</math>. This can be proven by setting WLOG <math>x \ge y \ge z</math> and bunching together terms that are nonnegative. Challenge: when does equality hold? When does equality hold in the problem?'' | ''Note: Schur's Inequality states that <math>x^r(x-y)(x-z) + y^r(y-z)(y-x) + z^r(z-x)(z-y) \ge 0</math>. This can be proven by setting WLOG <math>x \ge y \ge z</math> and bunching together terms that are nonnegative. Challenge: when does equality hold? When does equality hold in the problem?'' | ||
− | |||
− | |||
==See Also== | ==See Also== |
Latest revision as of 13:14, 7 June 2021
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.