Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Hint - restrict Z to {0,1,2} – Ed Pegg Oct 5 '11 at 4:50
up vote 7 down vote accepted
  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.

share|cite|improve this answer
Thank you! That makes perfect sense. Although I did get lost at step 4. I'm not sure how you minimized the probability function to get 1/4 – caligirl11 Oct 5 '11 at 4:59
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
Great I get it! Thank you so much! – caligirl11 Oct 5 '11 at 6:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.