1979 USAMO Problems/Problem 3

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?

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