Can you eat all the chocolates?

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]

And here is a far more elegant solution, courtesy of @rahmdphd on Twitter.
[Show Solution]

10 thoughts on “Can you eat all the chocolates?”

1. Guy D. Moore says:

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.

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

1. Dave Moran says:

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.

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

1. Dave Moran says:

Ah, now I see it. Thanks for the clarification.

2. MarkS says:

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

2. Nick Hlavacek says:

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.

1. MarkS says:

But this argument would apply even without the reset, and in that case, it gives the wrong answer. So it’s more subtle.

3. Mark Pilloff says:

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

1. Mark Pilloff says:

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.