# 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?