Opinion
Last byte

# Puzzled: Solutions and Sources

Last month (August 2009, p. 104) we posted a trio of brainteasers, including one as yet unsolved, concerning probability and intuition.
Posted

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)3 × (37/38)102, 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)8, 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.

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

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

### Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

### Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.