This week’s Riddler Classic is a neat puzzle about eating chocolates.
I have 10 chocolates in a bag: Two are milk chocolate, while the other eight are dark chocolate. One at a time, I randomly pull chocolates from the bag and eat them — that is, until I pick a chocolate of the other kind. When I get to the other type of chocolate, I put it back in the bag and start drawing again with the remaining chocolates. I keep going until I have eaten all 10 chocolates.
For example, if I first pull out a dark chocolate, I will eat it. (I’ll always eat the first chocolate I pull out.) If I pull out a second dark chocolate, I will eat that as well. If the third one is milk chocolate, I will not eat it (yet), and instead place it back in the bag. Then I will start again, eating the first chocolate I pull out.
What are the chances that the last chocolate I eat is milk chocolate?
Here is my original solution:
[Show Solution]
Let’s solve the more general version of the problem, where we initially have $M$ milk chocolates and $N$ dark chocolates in the bag. When referring to a state of the game, I will write a pair $(m,n)$, where $m$ and $n$ denote the number of milk chocolates and dark chocolates remaining, respectively. Let’s define a few functions given that we are currently in state $(m,n)$:
- $F(m,n)$: probability of winning given the state was just reset.
- $H_1(m,n)$: probability of winning if we just ate a milk chocolate.
- $H_2(m,n)$: probability of winning if we just ate a dark chocolate.
Note that $F(m,0)=H_1(m,0)=H_2(m,0) = 1$ for all $m\geq 1$, since we always win if there are only milk chocolates remaining. Also, we have that $F(0,n)=H_1(0,n)=H_2(0,n) = 0$ for all $n \geq 1$, since we always lose if there are only dark chocolates remaining.
We can write several recursive relationships relating these functions. First, once the game starts, we always eat the first chocolate we pick, and this determines our next state of the game:
\[
F(m,n) = \tfrac{m}{m+n} H_1(m-1,n) + \tfrac{n}{m+n} H_2(m,n-1)
\]Next, once we eat a chocolate, we will either continue to do so, or we will reset the state of the game, depending on which chocolate we pick next:
\begin{align}
H_1(m,n) &= \tfrac{m}{m+n}H_1(m-1,n) + \tfrac{n}{m+n}F(m,n) \\
H_2(m,n) &= \tfrac{m}{m+n}F(m,n) + \tfrac{n}{m+n}H_2(m,n-1)
\end{align}Let’s try to eliminate $H_1$ and $H_2$ in order to obtain a recursion in $F$ alone. Starting with the expression for $H_1$, we can recurse it backward to obtain:
\begin{align}
&H_1(m,n)\\
&= \tfrac{n}{m+n}F(m,n) + \tfrac{m}{m+n}H_1(m-1,n) \\
&= \tfrac{n}{m+n}F(m,n) + \tfrac{m}{m+1}\left( \tfrac{n}{m+n-1}F(m-1,n) + \tfrac{m-1}{m+n-1}H_1(m-2,n) \right) \\
&= \cdots
\end{align}Aggregating the terms and using the definition of the binomial coefficient, we can write the expression for $H_1$ compactly as
\[
H_1(m,n) = \frac{1}{\binom{m+n}{m}}\sum_{i=1}^m \binom{n+i-1}{n-1}F(i,n)
\]Similarly, we can recurse the expression for $H_2$ and obtain:
\[
H_2(m,n) = \frac{1}{\binom{m+n}{m}}\left[ 1 + \sum_{j=1}^n \binom{m+j-1}{m-1}F(m,j)\right]
\]The reason the expressions for $H_1$ and $H_2$ look slightly different in spite of all the symmetry in this problem is due to the different initial conditions; recall that $H_1(m,0)=H_2(m,0) = 1$, whereas $H_1(0,n)=H_2(0,n) = 0$.
Now substitute these expressions into our recursion for $F$ and after simplifying, we obtain:
\begin{align}
F(m,n) &= \tfrac{m}{m+n} H_1(m-1,n) + \tfrac{n}{m+n} H_2(m,n-1)\\
&= \frac{1}{\binom{m+n}{m}}\left[ 1 + \sum_{i=1}^{m-1} \binom{n+i-1}{n-1}F(i,n) + \sum_{j=1}^{n-1} \binom{m+j-1}{m-1}F(m,j)\right]
\end{align}Together with the initial conditions $F(i,0)=1$ and $F(0,j)=0$, this recursion gives us everything we need to find $F(m,n)$ for all $m$ and $n$.
Evaluating the first few terms, we discover something shocking… $F(m,n)$ appears to be exactly equal to $\tfrac{1}{2}$ for all values of $m$ and $n$! We can verify this by mathematical induction. Since our plan is to apply the above equation to generate all values of $F$, let’s assume that $F(i,j)=\tfrac{1}{2}$ for all terms on the right-hand side of the equation. Then we can compute:
\begin{align}
F(m,n) &= \frac{1}{\binom{m+n}{m}}\left[ 1 + \frac{1}{2}\sum_{i=1}^{m-1} \binom{n+i-1}{n-1} + \frac{1}{2}\sum_{j=1}^{n-1} \binom{m+j-1}{m-1}\right] \\
&= \frac{1}{\binom{m+n}{m}}\left[ 1 + \frac{1}{2}\left( \binom{m+n-1}{n}-1\right) + \frac{1}{2}\left( \binom{m+n-1}{m}-1 \right)\right]\\
&= \frac{1}{2\binom{m+n}{m}}\left[\binom{m+n-1}{n} + \binom{m+n-1}{m}\right] \\
&= \frac{1}{2\binom{m+n}{m}}\left[\binom{m+n-1}{n} + \binom{m+n-1}{n-1}\right] \\
&= \frac{1}{2\binom{m+n}{m}}\binom{m+n}{m} \\
&= \frac{1}{2}
\end{align}In the first step, we used the Hockey Stick Identity, in the third step we used the symmetry identity $\binom{n}{k}=\binom{n}{n-k}$, and in the fourth step we used the Pascal’s Triangle identity, namely $\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}$.
So amazingly, the probability of winning the game is independent of how many chocolates of each type are in the bag to begin with (as long as you have at least one of each type to begin with)! I have yet to come up with an elegant or intuitive way to understand why the answer should be independent of the initial number of chocolates, so if you have any ideas, leave them in the comments section below!
More types of chocolate?
Given the surprising solution to the previous problem, one might suspect that the pattern continues; if there are three different types of chocolates in the bag (say, milk chocolate, dark chocolate, and white chocolate), then perhaps the probability of eating a milk chocolate last is $\tfrac{1}{3}$? Unfortunately, this is not the case. Here are the recursions:
\begin{align}
F(m,n,p) &= \tfrac{m}{m+n+p} H_1(m-1,n,p) + \tfrac{n}{m+n+p} H_2(m,n-1,p) + \tfrac{p}{m+n+p} H_3(m,n,p-1) \\
H_1(m,n,p) &= \tfrac{m}{m+n+p}H_1(m-1,n,p) + \tfrac{n+p}{m+n+p}F(m,n,p) \\
H_2(m,n,p) &= \tfrac{n}{m+n+p}H_2(m,n-1,p) + \tfrac{m+p}{m+n+p}F(m,n,p) \\
H_3(m,n,p) &= \tfrac{p}{m+n+p}H_3(m,n,p-1) + \tfrac{m+n}{m+n+p}F(m,n,p)
\end{align}The initial conditions are a bit more complicated. For all $m\geq 1$:
\[
F(m,0,0)=H_1(m,0,0)=H_2(m,0,0)=H_3(m,0,0)=1
\]and for all $n\geq 0$ and $p \geq 0$ with $n+p \geq 1$, we have:
\[
F(0,n,p)=H_1(0,n,p)=H_2(0,n,p)=H_3(0,n,p)=0
\]A quick numerical check reveals that the solution is not $F(m,n,p)=\tfrac{1}{3}$. Here are a few values for $i=1,2,\dots$ and $j=1,2,\dots$:
\begin{align}
F(i,j,1) &= \begin{bmatrix}
\frac{1}{3} & \frac{13}{36} & \frac{3}{8} & \frac{23}{60} & \frac{7}{18} & \frac{11}{28} \\
\frac{5}{18} & \frac{7}{24} & \frac{71}{240} & \frac{107}{360} & \frac{25}{84} & \frac{25}{84} \\
\frac{1}{4} & \frac{31}{120} & \frac{31}{120} & \frac{115}{448} & \frac{685}{2688} & \frac{2041}{8064} \\
\frac{7}{30} & \frac{43}{180} & \frac{53}{224} & \frac{209}{896} & \frac{1237}{5376} & \frac{291}{1280} \\
\frac{2}{9} & \frac{19}{84} & \frac{299}{1344} & \frac{293}{1344} & \frac{493}{2304} & \frac{21343}{101376} \\
\frac{3}{14} & \frac{73}{336} & \frac{857}{4032} & \frac{199}{960} & \frac{10271}{50688} & \frac{40283}{202752} \\
\end{bmatrix} \\
F(i,j,2) &= \begin{bmatrix}
\frac{13}{36} & \frac{5}{12} & \frac{107}{240} & \frac{167}{360} & \frac{10}{21} & \frac{163}{336} \\
\frac{7}{24} & \frac{1}{3} & \frac{127}{360} & \frac{131}{360} & \frac{187}{504} & \frac{379}{1008} \\
\frac{31}{120} & \frac{53}{180} & \frac{4159}{13440} & \frac{203}{640} & \frac{31133}{96768} & \frac{52357}{161280} \\
\frac{43}{180} & \frac{49}{180} & \frac{2551}{8960} & \frac{1171}{4032} & \frac{2957}{10080} & \frac{4757}{16128} \\
\frac{19}{84} & \frac{65}{252} & \frac{929}{3456} & \frac{5507}{20160} & \frac{83627}{304128} & \frac{65203}{236544} \\
\frac{73}{336} & \frac{125}{504} & \frac{10393}{40320} & \frac{10529}{40320} & \frac{372011}{1419264} & \frac{13285}{50688} \\
\end{bmatrix} \\
F(i,j,3) &= \begin{bmatrix}
\frac{3}{8} & \frac{107}{240} & \frac{29}{60} & \frac{227}{448} & \frac{1405}{2688} & \frac{4309}{8064} \\
\frac{71}{240} & \frac{127}{360} & \frac{2561}{6720} & \frac{3567}{8960} & \frac{39623}{96768} & \frac{67351}{161280} \\
\frac{31}{120} & \frac{4159}{13440} & \frac{1}{3} & \frac{55961}{161280} & \frac{1275}{3584} & \frac{1283833}{3548160} \\
\frac{53}{224} & \frac{2551}{8960} & \frac{24679}{80640} & \frac{128069}{403200} & \frac{288059}{887040} & \frac{233803}{709632} \\
\frac{299}{1344} & \frac{929}{3456} & \frac{517}{1792} & \frac{105989}{354816} & \frac{1297237}{4257792} & \frac{3793873}{12300288} \\
\frac{857}{4032} & \frac{10393}{40320} & \frac{490247}{1774080} & \frac{1013213}{3548160} & \frac{3575315}{12300288} & \frac{1580549}{5381376} \\
\end{bmatrix}
\end{align}As anticipated, symmetry dictates that $F(k,k,k)=\tfrac{1}{3}$, and we do observe this in the numerical results above, but aside from that there is no immediately apparent pattern.
I didn’t put too much effort into trying to find a closed form for this case or the more general case with $k$ types of chocolates. If you think of a neat way to do it, leave a message in the comments section below!
And here is a far more elegant solution, courtesy of @rahmdphd on Twitter.
[Show Solution]
Let’s say the game is “reset” when no matter which chocolate we pick, we will eat it. Once we’ve eaten a chocolate of one type, then subsequent turns will either involve eating more of that same type of chocolate if we keep picking them, or the game will reset again if we pick differently. Let’s also define a “run” to be when you start from the reset state, and then keep picking chocolates of the same type until none are left.
Once we go on a run, the outcome of the game is decided: a run on milk chocolates means you only have dark chocolates remaining so you definitely lose. Likewise, a run on dark chocolates means you will definitely win.
The game starts in the “reset” state, and consists of some number of repeated resets (each time, with strictly fewer total chocolates in the bag), until we finally go on a run, and then the game ends.
If we are reset and have $(m,n)$ chocolates in the bag, what is the probability of a run on milk chocolates?
\[
\frac{m}{m+n} \cdot \frac{m-1}{m+n-1} \cdot \ldots \cdot \frac{1}{n+1} = \frac{m!n!}{(m+n)!}
\]Similarly, what is the probability of a run on dark chocolate?
\[
\frac{n}{m+n} \cdot \frac{n-1}{m+n-1} \cdot \ldots \cdot \frac{1}{m+1} = \frac{m!n!}{(m+n)!}
\]These two probabilities are exactly the same! And amazingly, this fact is always true regardless of how many chocolates are in the bag (as long as we have at least one of each type left).
So no matter how many resets we get, when the time comes for our run, we are always equally likely to run out of either chocolate. So the probability of winning the game is $\frac{1}{2}$.
This argument does not generalize to the case where there are $3$ types of chocolates, because the probability of running out of milk, dark, or white chocolates is:
\[
\frac{m!(n+p)!}{(m+n+p)!},\, \frac{n!(m+p)!}{(m+n+p)!},\, \frac{p!(m+n)!}{(m+n+p)!}
\]and these three quantities are not equal!