solutions and sources
Last month (February 2014) we posted three games in which
you were asked to pick a positive integer. The question in each was:
What is the highest number you should think about picking?
Here, we offer solutions to all three. How did you do?
DOI: 10.1145/2578281 Peter Winkler
1.found dollar. Alice and Bob are vying for a
found dollar, with lowest number the
winner and a tie winning it for neither.
Sadly, the only “Nash equilibrium” solution is for both players to choose “ 1”
and the dollar to go unclaimed—a mini
“prisoner’s dilemma.” Collaboration
could have won each of them 50 cents.
2.zero sum. Here, the writer of the lower
number wins $1 from the other player,
unless it is lower by only 1, in which
case the player with the higher number
would win $2 from the other player. A
tie would result in no money changing
hands. This problem was published by
Martin Gardner, appearing as Problem
11. 13 in his The Collossal Book of Short
Puzzles and Problems (W.W. Norton &
Co., New York, 2006). The Nash equilibrium solution would be to write “ 1,” “ 2,”
“ 3,” “ 4,” or “ 5” with probabilities 1/16,
5/16, 1/4, 5/16, and 1/16, respectively.
(Gardner did not provide a proof, but
it is not difficult to show this is a Nash
equilibrium strategy and, with a little
more work, the only one.) The highest
number either player should consider
writing is thus “ 5.”
3.swedish lottery. This game, which I included in
my book Mathematical Puzzles: A Co-
noisseur’s Collection (A K Peters Ltd.,
Natick, MA, 2001) as “Swedish Lot-
tery,” has the surprising property that
the equilibrium strategy calls for play-
ing every positive integer with positive
probability. There is no largest integer
you should consider playing. To see
this, imagine for the sake of reaching
a contradiction that there is a high-
est number you (and the other play-
ers) should ever play; call it number k.
When would you win playing k Only
when the other players choose the
same lower number. But if you played
k+ 1, you would win all those times
plus the times the other two players
both play k. k+ 1 is thus a better choice
than k, contradicting the assumption
that the strategy is a Nash equilibrium.
There is, in fact, a common Nash
equilibrium strategy for Alice, Bob,
and Charlie—calling for the num-
ber j to be selected with probability
( 1–r)r j– 1 where r is the root of a certain
cubic equation and approximately
0.543689. The probabilities for choos-
ing 1, 2, 3, and 4 are about 0.456311,
0.248091, 0.134884, and 0.073335, re-
spectively; the probability of choosing
a number greater than 100 is teeny. As
an experiment in 2010, I ran a Swedish
Lottery among 40 graduate students in
Dartmouth’s Computer Science Depart-
ment. The winning number was 6.
A much larger version—actually a
game a day for 47 straight days—was
run in Sweden in 2007 under the name
“Limbo.” The number of players each
day averaged 53,785; the lowest win-
ning number was 162, the highest
4, 465.Fo r more, see http://swopec.
All readers are encouraged to submit prospective
puzzles for future columns to email@example.com.
Peter Winkler ( firstname.lastname@example.org) is William morrill
Professor of mathematics and computer science,
at Dartmouth college, hanover, nh.
© 2014 acm 0001-0782/14/03 $15.00