The puzzle last week attracted enough interest that I thought you might like another puzzle based on probability. This one involves throwing dice. Assume you have a bucket of normal dice. You pick up a handful and throw them. How many dice should you throw to have an even chance of having each face (1-6) appear at least once?

This is a simple puzzle to state and not a difficult one to solve. I will give you one hint, or useful thought, before going into the solution. After you think about the hint, try to see how it fits with the puzzle before reading the solution.

Hint: The puzzle could have stated that you throw a single die N times. What is the minimum value of N that results in at least an even probability that each face will appear once?

The hint might not seem like such a great thing, but it should remind you that the value of each die being tossed (whether in a bunch or singly) is independent of the others. Unlike the puzzle of the gender of children, or the infamous Monty Hall paradox, I have not linked the probabilities.

So if you have thought about it and have not looked ahead, here is one way to find the answer: Start by realizing that the first toss is a freebie. That is, you do not care what number it is. Anything is okay. The first toss gets you one side.

On the second toss, what is the probability that any of the other 6 sides will come up? Since each side has a 1/6 probability, then the probability of the second toss not being the same as the first one is 5/6. That looks good, but to go any further, we need to know that the expected number of tosses (events) is simply the inverse of the probability. That is for a fair coin, the probability of either side is 1/2. Therefore the expected number of coin tosses to get a particular side is 1/(1/2) or 2. Similarly, the probability of any face on a die coming up is 1/6. Therefore the expected number of tosses to get that face is 1/(1/6) or 6. The same thing holds for the probability of not getting a particular side. Since this probability is 5/6, then the expected number of events is 6/5. That number of tosses gets added to the 1 of the first toss.

Next we ask what is the expected number of tosses to get any sides other than the first two. The probability of getting either of the first two on a single throw is 1/3 (why?). Therefore the probability of not getting either is 2/3 (why?). The expected number of tosses is the inverse or 3/2. Add this to the previous sum.

Similarly the probability of not getting any of the first three is 1/2, so we add another two tosses.

This brings us to the fifth side. The probability of not getting any of the first four sides in 1/3 (why?). So we add another three tosses.

The last side is easy. The probability of not getting any of the preceding 5 sides is 1/6. So 6 throws are the expected number of tosses to get the last side.

When we add them all up, we get 14.7 tosses to give even odds of seeing each face at least once. Since you cannot throw 0.7 die, round up to 15. So when you reach into the bucket, if you grab and throw 15 dice, the odds are slightly better than even that each side will appear at least once.

*In response to the interest my original tutorial generated, I have completely rewritten and expanded it. Check out the tutorial availability through Lockergnome. The new version is over 100 pages long with chapters that alternate between discussion of the theoretical aspects and puzzles just for the fun of it. Puzzle lovers will be glad to know that I included an answers section that includes discussions as to why the answer is correct and how it was obtained. Most of the material has appeared in these columns, but some is new. Most of the discussions are expanded compared to what they were in the original column format.*

[tags]probability, statistics, decision theory[/tags]