# Dynamic subtraction game

I came across the following dynamic subtraction game:

There is one pile of n chips. The ﬁrst player to move may remove as many chips as desired, at least one chip but not the whole pile. Thereafter, the players alternate moving, each player not being allowed to remove more chips than his opponent took on the previous move. What is an optimal move for the ﬁrst player if n = 44? For what values of n does the second player have a win?

Now, I know how to solve basic subtraction games, i.e., when both the players are allowed the same set of moves throughout the game (e.g., subtract only 1, 2, or 3 throughout the game). But in the game mentioned above, this set of possible numbers for subtraction is not fixed. I have no clue how to go about solving this question. Any kind of help would be appreciated.

• Who wins the game? – David Richerby Nov 8 '13 at 13:14
• A player who cannot move loses the game, and the other player wins the game. In this game, you cannot move only if the pile has size 1, so you win if you succeed in reducing the pile to a single chip. – Yuval Filmus Nov 8 '13 at 22:25

You can find the winner (and even the Sprague-Grundy function) using dynamic programming. Each state of your game consists of a pair $(n,B)$, where $n$ is the number of chips, and $B$ is an upper bound on how many chips you're allowed to remove. I'll let you figure out the edges of this dag and the starting state. Now you scan the graph from the sinks up: a sink (state with no outgoing edges) is a LOSE state (from the point of view of the player whose turn it is to play). A state leading only to WIN states is a LOSE state, otherwise it's a WIN state, and any edge pointing at a LOSE state is a winning move.
It's probably more challenging to find a general formula for which player wins the game given $n$, but one way would be to compute it empirically for several values of $n$ (or more generally, of $n$ and $B$), figure out a formula, and prove your formula.