Difference between revisions of "1979 USAMO Problems/Problem 3"

Latest revision as of 13:14, 7 June 2021

Problem

$a_1, a_2, \ldots, a_n$ is an arbitrary sequence of positive integers. A member of the sequence is picked at random. Its value is $a$ . Another member is picked at random, independently of the first. Its value is $b$ . Then a third value, $c$ . Show that the probability that $a + b +c$ is divisible by $3$ is at least $\frac14$ .

First Hint

The given problem is equivalent to proving that $4(x^3 + y^3 + z^3 + 6xyz) \ge (x + y + z)^3$ .

Second Hint

Try proving this inequality for all nonnegative real numbers x, y, z; not just positive integers.

Final Hint

Prove that $x^3 + y^3 + z^3 + 3xyz \ge x^2(y+z) + y^2(x+z) + z^2(x+y).$

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 $x^3 + y^3 + z^3 + 6xyz \ge x^2(y+z) + y^2(x+z) + z^2(x+y).$ Now, we attempt to prove that $x^3 + y^3 + z^3 + 3xyz \ge x^2(y+z) + y^2(x+z) + z^2(x+y).$ 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 $x^r(x-y)(x-z) + y^r(y-z)(y-x) + z^r(z-x)(z-y) \ge 0$ . This can be proven by setting WLOG $x \ge y \ge z$ and bunching together terms that are nonnegative. Challenge: when does equality hold? When does equality hold in the problem?

@@ Line 2: / Line 2: @@
 <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 \plus{ } b \plus{ } 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==
+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==
 {{USAMO box|year=1979|num-b=2|num-a=4}}
+{{MAA Notice}}
+[[Category:Olympiad Combinatorics Problems]]

1979 USAMO (Problems • Resources)
Preceded by Problem 2	Followed by Problem 4
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

Page

Toolbox

Search