# Show that $P(X+Y+Z\text{ is a multiple of }3)\ge 1/4$

Suppose a box contains tickets, each labeled by an integer. Let $X,Y$ and $Z$ be the results of draws at random with replacement from thw box. Show that no matter what the distribution of numbers in the box,

$$P(X+Y+Z\text{ is a multiple of }3)\ge 1/4\;.$$

Hint: think about remainders when dividing by 3

-
Hint - restrict Z to {0,1,2} –  Ed Pegg Oct 5 '11 at 4:50

1. $X$, $Y$ and $Z$ follow the same distribution.
2. Let $p_0 = \mathbb{P}( X\mod 3 \equiv 0)$, $p_1 = \mathbb{P}( X\mod 3 \equiv 1)$ and $p_2 = \mathbb{P}( X\mod 3 \equiv 2)$ and $p_0+p_1+p_2=1$.
3. Now $\mathbb{P}( X + Y + Z \mod 3 \equiv 0) = p_0^3 + p_1^3 + p_2^3 + 6 p_0 p_1 p_2$, because there are 9 triples leading to the desired outcome: $[0,0,0]$, $[1,1,1]$, $[2,2,2]$, and 6 permutations of $[0,1,2]$.
4. Now minimize $p_0^3 + p_1^3 + p_2^3 + 6 p_0 p_1 p_2$ subject to constraints $p_0, p_1, p_2 \ge 0$ and $p_0+p_1+p_2=1$, which yields exactly $\frac{1}{4}$, that proves the result.
Minimum can occur either in the bulk of the constrained region, or on the boundaries. For the bulk, make substitution $p_0 = 1- p_1 -p_2$ in the function $f = p_0^3+p_1^3+p_2^2 + 6 p_0 p_1 p_2$, then write extrema equations. They will be $3 (2p_1 + p_2 -1) (3 p_2 -1) = 0$ and $3(3p_1-1)(2p_2 + p_1 -1) =0$. Solve to find $p_0=p_1=p_2 = \frac{1}{3}$ and substitute back, this gives $f=\frac{1}{3}$. Value at the boundaries on constraints should also be checked. For the boundary, set $p_0 =0$, then $p_2=1-p_1$. Minimum occurs at $p_1=p_2 = 1/2$ with $f=1/4$. This is the true minimum. –  Sasha Oct 5 '11 at 5:41