Difference between revisions of "1979 USAMO Problems/Problem 3"
m |
(→Solution) |
||
(10 intermediate revisions by 3 users not shown) | |||
Line 3: | Line 3: | ||
<math>a_1, a_2, \ldots, a_n</math> is an arbitrary sequence of positive integers. A member of the sequence is picked at | <math>a_1, a_2, \ldots, a_n</math> is an arbitrary sequence of positive integers. A member of the sequence is picked at | ||
random. Its value is <math>a</math>. Another member is picked at random, independently of the first. Its value is <math>b</math>. Then a third value, <math>c</math>. Show that the probability that <math>a + b +c</math> is divisible by <math>3</math> is at least <math>\frac14</math>. | random. Its value is <math>a</math>. Another member is picked at random, independently of the first. Its value is <math>b</math>. Then a third value, <math>c</math>. Show that the probability that <math>a + b +c</math> is divisible by <math>3</math> is at least <math>\frac14</math>. | ||
+ | |||
+ | ==First Hint== | ||
+ | The given problem is equivalent to proving that <math>4(x^3 + y^3 + z^3 + 6xyz) \ge (x + y + z)^3</math>. | ||
+ | |||
+ | |||
+ | |||
+ | ==Second Hint== | ||
+ | Try proving this inequality for all nonnegative real numbers x, y, z; not just positive integers. | ||
+ | |||
+ | ==Final Hint== | ||
+ | Prove that <math>x^3 + y^3 + z^3 + 3xyz \ge x^2(y+z) + y^2(x+z) + z^2(x+y).</math> | ||
==Solution== | ==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 <math>x^3 + y^3 + z^3 + 6xyz \ge x^2(y+z) + y^2(x+z) + z^2(x+y).</math> Now, we attempt to prove that <math>x^3 + y^3 + z^3 + 3xyz \ge x^2(y+z) + y^2(x+z) + z^2(x+y).</math> 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 <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== | ||
{{USAMO box|year=1979|num-b=2|num-a=4}} | {{USAMO box|year=1979|num-b=2|num-a=4}} | ||
+ | {{MAA Notice}} | ||
[[Category:Olympiad Combinatorics Problems]] | [[Category:Olympiad Combinatorics Problems]] |
Latest revision as of 14: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.