Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
Hint - restrict Z to {0,1,2} –  Ed Pegg Oct 5 '11 at 4:50
add comment

1 Answer

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|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
add comment

Your Answer

 
discard

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.