Sign In

Communications of the ACM

Last byte

Puzzled: Lowest Number Wins


View as: Print Mobile App ACM Digital Library Full Text (PDF) In the Digital Edition Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook
hand holding a pen

Credit: Shutterstock.com

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

Author

Peter Winkler (puzzled@cacm.acm.org) is William Morrill Professor of Mathematics and Computer Science at Dartmouth College, Hanover, NH.

Back to Top

Footnotes

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.


Copyright held by Author/Owner(s).

The Digital Library is published by the Association for Computing Machinery. Copyright © 2014 ACM, Inc.