## Dollar Nim

*June 27, 2011 at 11:19 pm* *
6 comments *

*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.

Entry filed under: Uncategorized. Tags: coin, dollar, Nim, postaweek2011, Survivor.

1.Denise | July 7, 2011 at 12:16 pmThat’s a great game! I’ve played Subtraction Nim from 100 using {5, 10, 15}, but I never thought to use coin values.

I’m writing a book of arithmetic games. Would your wife mind if I include this? And if I may use it, then how would she like to be credited?

2.venneblock | July 7, 2011 at 9:00 pmI like Subtraction Nim from 100 using {5, 10, 15}. That reduces to a pile of 20 using {1,2,3}, which is easy enough… but most kids wouldn’t recognize it in this disguised form.

3.Denise | July 29, 2011 at 10:10 amWe had played one-pile Nim earlier in the school year, and I did have one boy (about 4th grade, if I remember correctly) who recognized the equivalence. He is now in college, studying engineering.

4.How many Mathematicians Does It Take to Change A Light Bulb? « Mathspig Blog | September 14, 2012 at 6:05 am[...] not solving problems, telling jokes, playing gameswith his sons, managing projects for the National Council of Teachers of Mathematics, or finding fun [...]

5.spoonietreasure Jennifer | February 8, 2014 at 6:03 pmTry adding to an empty pot. The one to put the final coin in wins the pot.

6.venneblock | February 9, 2014 at 3:47 pmLove it! We had been experimenting with similar rules. Our issue was that this could result in an unfair amount in the pot by each player (if this was truly meant to be a gambling game). Our solution was that each person should start with the same number/value of coins… and when a person runs out of a certain type of coin, well, tough noogies.