NIM with Cash

Abstract

NIM(a1, ..., ak; n) is a 2-player game where initially there are n stones on the board and the players alternate removing either a1 or ... or ak stones. The first player who cannot move loses. This game has been well studied. For example, it is known that for NIM(1, 2, 3; n) Player II wins if and only if n is divisible by 4. These games are interesting because, despite their simplicity, they lead to interesting win conditions. We investigate an extension of the game where Player I starts out with d1 dollars, Player II starts out with d2 dollars, and a player has to spend a dollars to remove a stones. This game is interesting because a player has to balance out his desire to make a good move with his concern that he may run out of money. This game leads to more complex win conditions then standard NIM. For example, the win condition may depend on both what n is congruent to mod some M1 and on what d1 - d2 is congruent mod some M2. Some of our results are surprising. For example, there are cases where both players are poor, yet the one with less money wins. For several choices of a1, ..., ak we determine for all (n, d1, d2) which player wins.