Sign In

Communications of the ACM

Last byte

Puzzled: Solutions and Sources


View as: Print Mobile App ACM Digital Library Full Text (PDF) In the Digital Edition Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook
Dartmouth College Professor of Mathematics and of Computer Science Peter Winkler

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

ueq01.gif

which, when divided by the total of 66 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 362 possible outcomes, the number yielding a sum of seven twice is 62 = 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 situationwhere wins by one party tend to exhibit smaller margins than wins by the otherthat expectation and probability can produce opposing results.

Back to Top

Author

Peter Winkler (puzzled@cacm.acm.org) is William Morrill Professor of Mathematics and Computer Science, at Dartmouth College, Hanover, NH.

Back to Top

Footnotes

ALL readers are encouraged to submit prospective puzzles for future columns to puzzled@cacm.acm.org.


©2013 ACM  0001-0782/13/03

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from permissions@acm.org or fax (212) 869-0481.

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