## Posts tagged ‘Survivor’

### Dollar Nim

*The following post was featured at the NYTimes Numberplay blog during the week of August 8‑15, 2011.*

One-Pile Nim (a.k.a., Static Nim) is a game in which there is a pile of *n* objects, and each player can take up to *k* objects on her turn. The player who removes the last object wins. For example, on the TV show *Survivor: Thailand* in October 2002, the contestants were given an “immunity challenge” in which there were 21 flags, and a team could remove 1, 2, or 3 flags on a turn. (Using the notation above, *n* = 21 and *k *= 3.) Avinash Dixit claims that “the actual players [on *Survivor: Thailand*] got almost all of their moves wrong,” but the strategy for winning this game is not terribly difficult to figure out. If you’re not familiar with the game, you might enjoy determining the strategy on your own, so I won’t spoil your fun.

While riding back from a camping trip yesterday, my wife was keeping my sons amused by playing mental math games with them. However, she was using mostly drill-and-kill exercises, where she would state an expression like 21 – 6, and one of them would shout, “15!” Before I was able to suggest that she play a game that involved more strategy and less rote mathematics, she offered the following.

- Start with $1, or with 100¢, if you prefer.
- On alternating turns, players can remove any coin they like. (Well, technically, players remove a number of cents equal to the value of one of the four common U.S. coins — quarter, dime, nickel, penny — but such an overly complicated statement of the rules would have confused my sons.)
- The player who reduces the value to 0¢ wins.

That is, *n* = 100, and a player must choose to remove a value from the set {1, 5, 10, 25}.

I was duly impressed by my wife’s creation. (By “my wife’s creation,” I mean to refer to the game she made up, not to my sons, though the moniker would be equally applicable to the latter, and I must admit that I am often duly impressed by my sons, too.) It was a version of Nim that I had never seen before, and the optimal strategy was not obvious to me. Moreover, it had the characteristics of activities that I love to use with young kids: it causes them to practice some useful basic skill (in this case, calculating change for a dollar) for the purpose of trying to win a strategy game with more sophisticated mathematics.

My two sons, my wife, and I played Dollar Nim several times. During our third game, my wife took a dime to leave me with 29¢. “Daddy’s going to win,” Alex declared. Sure enough, I took a quarter to leave 4¢, and the outcome was decided. Both Alex and Eli had realized that if one of us was able to reduce the amount to 4¢, that person would win — everyone would be forced to take a penny.

Analyzing this game for two players is not terribly difficult, though once I had done it, I was intrigued by the patterns that appear in the optimal strategy. Analyzing the game for four players is a bit more difficult.

In the post on the *NYTimes NumberPlay *blog, Pradeep Mutalik offered the following extension question:

Since Dollar Nim is played with real money, it makes sense for the participants to keep the change they remove. This confers a reward for removing larger denominations. To offset this, the winner must be given an extra monetary reward. What should be the

minimumprize money for the two-player game so that no matter what happens, the winner comes out ahead?

I’ll leave it as an exercise for the reader to determine the optimal strategy for the two- and four-player versions of this game, as well as to determine the answer to Pradeep’s question.

**[Update, 6/30/11]** The sequence of “unsafe” values for two-player Dollar Nim is now listed as A192333 in the Online Encyclopedia of Integer Sequences.