last byte

DOI: 10.1145/1562164.1562191
Peter Winkler
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.

1.Last Night in Vegas 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.

abilities 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 ½. The argument works with 100 replaced by any number greater than one.

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 prob-

3.Random arcade Conjecture. My intuition, and perhaps yours, too, suggests that the best possible situation is if each gum-ball 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?

All readers are encouraged to submit prospective puzzles for future columns to [e-mail].

Peter Winkler ( [e-mail]) is Professor of Mathematics and of Computer science and Albert Bradley Third Century Professor in the sciences at Dartmouth College, Hanover, nH.