Communications of the ACM

Last byte

Puzzled: Solutions and Sources

By Peter Winkler
Communications of the ACM, September 2009, Vol. 52 No. 9, Page 110
10.1145/1562164.1562191
Comments (1)

Solution. This puzzle was passed to me by math-puzzle connoisseur Elwyn Berlekamp during the seventh Gathering for Gardner (http://www.g4g4.com/), March 2006, in Atlanta, GA, one of an ongoing series of meetings dedicated to the great puzzle proselytizer Martin Gardner. It later appeared in Berlekamp's and Joe Buhler's "Puzzles Column" in The Emissary newsletter (http://www.msri.org/communications/emissary/index_html) published by the Mathematical Sciences Research Institute, Berkeley, CA.

The idea is that most people have pretty good intuition concerning the "law of large numbers," which says roughly that repeated random events, like betting on roulette, tend in the long run to produce approximately the result predicted by probabilities. At a Las Vegas roulette table in the puzzle, each single-number bet loses an average of $1 - 1/38 × $36 = $1/19, or about five cents. Thus, a run of 105 bets loses an average of $5.53 in total, even if it is your birthday. Sounds like your probability of coming out ahead should be small.

However, averages don't tell the whole story, as we are reminded by the legend of the statistician who drowned in a river of average depth three inches. As it turns out, 105 bets are not nearly enough to invoke the law of large numbers. Much of the time (exact probability is (105 × 104 × 103 / 3 × 2 × 1) × (1/38)³ × (37/38)¹⁰², or around 0.225) you will win exactly three times, putting you ahead by a hair. You would then have $108 for your $105 investment. A few more calculations, and you'll find that the probability of coming out ahead is about .5254, or more than a half.

This doesn't mean you have Las Vegas by the throat. Failing to get your three wins, you'd lose a lot of your money, on average, paying $5.53 for your roulette adventure.

For a more extreme example of this phenomenon, suppose you approach the roulette table with $255 but need $256 to pay your registration fee for an ACM conference at the same hotel. Your best course would be to plan on betting $1, then $2, then $4, $8, $16, $32, $64, and finally $128 on red (or black). The first time you win, you collect double your stake and quit immediately, now with exactly the $256 you need. You fail only if you lose all eight bets (and all your money). But failure occurs with probability only (20/38)⁸, or less than .006, so you'd get to attend the conference more than 99.4% of the time.

You could also then quit gambling for the rest of your life. Highly recommended.

Back to Top

2. Fully Booked Aircraft

Solution. I heard this puzzle at the fifth Gathering for Gardner, from Ander Holroyd of Microsoft Research. It seems to have been circulating for years, though it often happens that people who have heard it before are mystified the second time around as well. The key is that the last empty seat must have been the one assigned to either the last passenger or to the first. However, just because we have only two cases doesn't mean the probabilities are necessarily equal, as victims of the Monte-Hall-and-the-three-doors puzzle can testify.

Here, however, the two seats play identical roles in the boarding process; each passenger is as likely to take one seat as the other, as long as both are free. Hence, the probability that it is indeed his/her own seat that the last passenger finds open is exactly 1/2. The argument works with 100 replaced by any number greater than one.

Back to Top

3. Random Arcade

Conjecture. My intuition, and perhaps yours, too, suggests that the best possible situation is if each gumball machine disgorges n+1 gumballs with probability 1/(n+1), otherwise none. That way, the player putting a coin in each machine would succeed as long as at least one of the n machines pays off. What is the player's success probability in this scenario?

Failure requires that each machine refuses to cooperate, which happens with probability (1 - 1/(n+1))ⁿ. The player succeeds with probability one minus that expression. For n equals one through six, the formula gives success probabilities 1/2, 5/9, 37/64, 369/625, 4,651/7,776, and 70,993/117,649; to the nearest thousandth, it would be .500, .556, .578, .590, .598, and .603. The numbers approach 1 - 1/e ~ .632, from below, as n increases. Thus, the answer appears to be 1 - 1/e.

However, no one has managed to prove that you can never do better than 1 - 1/e. The puzzle's creator, Uriel Feige of the Weizmann Institute of Science, Rehovot, Israel, has shown that the success probability can never exceed 12/13 ~.923. Can you get a better bound?

Back to Top

Back to Top

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

---

Comments

---

Displaying 1 comment