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!
Hi Laurent,
While I don’t have an easy intuitive explanation why the chance is 1/2 if both
m=number of milk chocolates and
d=number of dark chocolates
are positive, I have a much simpler way to see the induction.
In particular, I don’t need to introduce or compute the H_1 and H_2 functions.
Suppose that, for all positive m and d with m+d < N, we have F(m,d) = 1/2.
Consider m and d, each positive, and adding to N.
Randomly arrange the N candies, and take this to be the order to pick them -until- we
reach a chocolate of the opposite sort as last time. Either
1) all m milk chocolates come first, then all d dark. In this case you will end with a dark chocolate.
2) all d dark chocolates come first, then all m milk. In this case you will end with a milk
chocolate. Note that 1) and 2) are exactly equally likely, eg, the probability of each is m! d! / N!
3) all other cases. Then we will eat some of one of the flavors, leaving a new (m',d') which
are each nonzero and with m' + d' < N. By the induction hypothesis, the chance to end with
a milk chocolate is F(m',d') = 1/2.
Averaging these three cases with their respective probabilities gives a 1/2 chance to end on
a milk chocolate piece.
I updated my write-up to include the very elegant solution by @rahmdphd. It solves the problem in a few lines and also gives an intuitive explanation!
Laurent,
I’m not completely sold by the elegant explanation you published from @rahmdphd because I think it’s missing a step.
The argument starts with assuming we’re in state (m, n) and asking what’s the probability of a run from that state. But it doesn’t take into account how we got to (m, n). If the last chocolate we ate to get to (m, n) was dark, then a run on milk chocolates would have to start with drawing two milk chocolates in a row (the first one would be put back in the bag, and then you’d have to draw another milk chocolate to start a run on milk chocolates). The equations you wrote down for the probability of a run going either way assume that the (m, n) state doesn’t care how we got there, which isn’t true.
I edited my write-up to try and clarify.
When I said we’re in state $(m,n)$, I meant that we have just “reset”, i.e. no matter which chocolate we pick next we will eat it. From that point forward, there are three possible outcomes:
1) we will run out on milk chocolate and lose (only ever pick milk chocolates from now on)
2) we will run out on dark chocolate and win (only ever pick dark chocolates from now on)
3) we will not run out, so we will end up with another reset and the game continues.
Options 1 and 2 are always equally likely and are also the only ways the game can end. Therefore the game is equally likely to end with either outcome.
Ah, now I see it. Thanks for the clarification.
We don’t even need to compute the probabilities. It’s enough to note that, at each selection, each remaining piece is equally likely; therefore the probability of drawing m milk and n dark, in any order, must be the same. (The only two relevant orders being all milk followed by all dark, and vice versa.)
An intuitive way to look at this (and one that doesn’t really involve any math) is that you’re balancing a scale. For any amount of chocolate where you have some amount of dark and some milk, your odds of picking dark or milk depends on how many of each there are. If there are more dark, then your odds of picking dark first and going on a streak of dark are higher (obviously). Thus the odds are that you’re always moving towards having a balance of equal numbers of each type. You might go on a streak that unbalances the scale (because the chance of picking either type is never zero until that type is all gone), but that just makes it more likely that your next streak will act to balance it again. Once it’s balanced, you have an even chance of picking either type. The next pick will unbalance it again, and the bias will move towards balance. That’s why there’s always a 50/50 chance no matter how many of each you start with.
But this argument would apply even without the reset, and in that case, it gives the wrong answer. So it’s more subtle.
I’m fascinated by this problem but I am not convinced by the argument that, with (m,n) milk and dark chocolates left in the bag, the probability of a run on either flavor is simply m! n! / (m+n)!. This would be true if you simply ate whichever chocolate you drew. However, the chocolates are “sticky” and thus some sequences of eaten (not drawn!) chocolates are more likely than others. In fact, for the problem as posed with 8 darks and 2 milks, you can work out that the probability of a run of all 8 darks is 11/54 and that the probability of a run of both milks is 34/810. (Hence the other ~75% of the time you get a mixed sequence.) These expectations are easy to validate with a simulation of the game: https://repl.it/@MarkPilloff2/RiddlerChocolates#Main.java
Aaaaand, what I said is irrelevant, as I misunderstood the meaning of a run. The probabilities I quoted are for eating all of the darks (milks) before any of the opposite flavor, irrespective of how many runs it takes. So you could draw 4 darks, 1 milk (thrown back), and 4 more darks. But that’s not one run, it’s three. The originally shared argument is valid and hopefully my incorrect objection will be illuminating to anyone else who misunderstood.