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 puzzled@cacm.acm.org.
Peter Winkler ( puzzled@cacm.acm.org) is Professor of
Mathematics and of Computer science and Albert Bradley
Third Century Professor in the sciences at Dartmouth
College, Hanover, nH.