[Solved]: Dynamic subtraction game

Problem Detail: 

I came across the following dynamic subtraction game:

There is one pile of n chips. The first 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 first 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.

Asked By : user11119

Answered By : Yuval Filmus

Hint: A player loses if they are presented with a pile of size 1. If presented with a larger pile, what should you do if it's the first move of the game?

---

Here is a more general solution, which will be applicable in other cases.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16820