last byte
DOI: 10.1145/1536616.1536642
Peter Winkler
Puzzled
Probability and Intuition
Welcome to three new puzzles. Solutions to the first two will be published next
month; the third is (as yet) unsolved. In each puzzle, the issue is how your intuition
matches up with the mathematics.
1.It is your last night in Las Vegas as you celebrate
your 29th birthday. Standing
at the roulette table with $105
in your pocket, you resolve to
make 105 successive $1 bets
on the number 29. You will
win $36 (minus your $1 bet)
each time the ball lands on
“ 29,” but, unfortunately, this
happens with probability only
1/38; the rest of the time you
simply lose your dollar. Use
your intuition. What is the
probability that, after the 105
bets, you come out ahead?
2.A hundred people board a fully booked aircraft.
Unfortunately, the first person
in line somehow loses his/her
boarding pass while entering
and takes a random seat. Each
successive passenger then
sits in his/her proper seat,
if available; otherwise, each
one rather wimpily takes a
random vacant seat. Again,
use your intuition. What is
the probability that the last
passenger finds the properly
assigned seat unoccupied?
3.The Random Arcade, a favorite hangout of
local video gamers, boasts a
line of n gumball machines.
Each machine is unpredictable
but produces an average of
one gumball each time it is
operated; for example, it may
be that Machine no. 1 produces
two balls half the time and the
rest of the time none at all.
What is the maximum
possible probability that if you
put a coin in each machine, you
will be rewarded with a total of
more than n gumballs?
This puzzle (stated in terms
of sequences of independent
random variables) is due to
Uriel Feige of the Weizmann
Institute of Science, Rehovot,
Israel. 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 it gives
nothing. That way, you succeed
as long as at least one of the n
machines pays off. What is
your success probability?
Failure requires that every
machine refuses to cooperate,
happening with probability
( 1 – 1/(n+ 1))n. So you succeed
with probability one minus
that expression. For n = 1
through 6, this gives success
probabilities of 1/2, 5/9, 37/64,
369/625, 4,651/7,776, and
70,993/117,649; to the nearest
thousandth, these numbers are
.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, despite some
serious effort, no one has
managed to prove that you can’t
do better than 1 – 1/e. Feige
himself showed that the success
probability can never exceed
12/13 ∼ .923. Can you improve
on his bound?
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.
