Last byte

Puzzled: Lowest Number Wins

  1. Article
  2. Author
  3. Footnotes
hand holding a pen

Each of these puzzles involves a symmetric game. You will be asked about your best strategy, but what does "best strategy" mean? Here, we want a strategy that is a "Nash equilibrium" for all players; that is, one with the property that if it is followed by all other players, you can do no better than follow it yourself. Often, such a strategy requires that players do some randomization; for example, in the familiar game "Rock, Paper, Scissors," the Nash equilibrium strategy requires each player to choose rock, paper, or scissors with equal probability. As in "Rock, Paper, Scissors," plays in the games here are done simultaneously, with no collaboration allowed, so every man/woman for him/herself. For solutions and sources, see next month’s column.

  1. Having found a dollar bill on the street, Alice and Bob each write down a positive integer. Lowest integer wins the dollar. If they each write the same number, the dollar is torn up. What is the highest integer you, as Alice, should consider writing down?
  2. No dollar is found this time. Alice and Bob instead play a "zero-sum game" with their own money. Each again writes down a positive integer. Lowest integer wins $1 from the other player, unless it is lower by exactly 1; in that case, the player with the higher number wins $2 from the other player. If the players happen to choose the same number, no money changes hands. What is the highest integer you, as Alice, should consider writing down?
  3. Three players this time, with a $10 prize to be given to the player who writes down the lowest number not written down by any other player. For example, if Alice and Bob each write "1" and Charlie writes "2," Charlie wins the $10. If Alice writes "2," Bob "3," and Charlie "5," Alice wins. If all three write the same number, the prize goes unclaimed. What is the highest integer you, as Alice, should consider writing down?

Back to Top

Back to Top

    Corrections to "Solutions and Sources" (Dec. 2013) to "Coin Flipping" (Nov. 2013). Three careful readers pointed out there are 12, not 10 (as we said in the solution to Problem 1) head-tail sequences of length 5 that take on average only 32 flips to occur. In addition, Joseph Skudlarek found a sequence (HTTHH or its complement THHTT) that gets the first player a better than 1/3 chance to win in Problem 2, 9/26, to be exact.

    Readers are encouraged to submit prospective puzzles for future columns to puzzled@cacm.acm.org.

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

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.

Learn More