7
$\begingroup$

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

  • 0
    Hint - restrict Z to {0,1,2}2011-10-05

1 Answers 1

7
  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.

  • 0
    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/42011-10-05
  • 0
    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.2011-10-05
  • 0
    Great I get it! Thank you so much!2011-10-05