Communications of the ACM

Last byte

Puzzled: Solutions and Sources

By Peter Winkler
Communications of the ACM, March 2013, Vol. 56 No. 3, Page 102
10.1145/2428556.2428578
Comments (2)

You were asked to compute the probability of getting exactly four different numbers when tossing six dice (each with faces numbered 1 through 6). The answer, surprisingly (to me, at least, when I discovered it by accident) is that it is over 50%; that is, rolling a "four" this way is more likely than all other outcomes combined. The calculation is easy to mess up, by over- or undercounting. Four different numbers can be produced in two general ways: three of one number, and one each of three other numbers; or two each of two numbers, and one each of two others. For each of these ways, we first pick a "pattern" (such as ABCBBD), then assign numbers left to right. The total number of ways to roll a "four" is

which, when divided by the total of 6⁶ ways to roll the dice, gives approximately 50.154321%.

Back to Top

2. Four of a kind vs. six different

This and the next puzzle were both inspired by correspondence with my longtime friend Bob Henderson of Mason, MI. A single die is rolled until Alice sees all the faces or Bob sees four of a kind. One of them must win by the 16th roll; in the slowest case, 15 rolls would consist of three of each of five faces, and none of the sixth. Who is more likely to win? It turns out Bob has a sizeable advantage. The easiest way to see this is to prove by induction that after any number of rolls, he is more likely to have won than Alice. Surprised? I often see eyebrows go up at the idea that most of the time (over 63%, it turns out) some number will appear four times before some other number appears even once. This outcome is related to the oft-cited observation that runs of heads or tails in a sequence of coin flips tend to be longer than people expect.

Back to Top

3. Seven-seven vs. eight-seven

A pair of dice is rolled repeatedly, with Alice gunning for two 7s in a row and Bob for an 8 followed immediately by a 7. Which is smaller: average time for Alice to succeed or average time for Bob to succeed? And who is more likely to get their wish first? Suppose the dice-pair is rolled twice. Of the 36² possible outcomes, the number yielding a sum of seven twice is 6² = 36. The number of outcomes yielding 8 then 7 is only 5 × 6 = 30. Looks good for Alice, one might think. It takes on average six rolls to get a 7 and a seventh roll to try to duplicate it; Alice will go through this procedure an average of six times, so, overall, it takes an average of 7 × 6 = 42 rolls for her to get what she wants. (We are making heavy use here of the fact that if you try something repeatedly that has probability of success p, it will take you on average 1/p trials to succeed.) The calculation for Bob is trickier since if he rolls an 8 then misses by rolling a second 8, he immediately gets another try. Doing the math, it works out to an average of 43.2 rolls to satisfy Bob. But another calculation shows that when Alice and Bob compete head to head on the same rolls, Bob wins with probability 35/66 > 53%. But how can this be? Perhaps the best intuition is provided by rolling the dice until both parties succeed. When Alice wins (that is, 7-7 comes up before 8-7) it is always by at least two rolls. But Bob can win by just one roll, when 8-7-7 comes up in that order. It is in just this kind of situation—where wins by one party tend to exhibit smaller margins than wins by the other—that expectation and probability can produce opposing results.

Back to Top

Back to Top

The Digital Library is published by the Association for Computing Machinery. Copyright © 2013 ACM, Inc.