1
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Who wins the game? $\endgroup$ – David Richerby Nov 8 '13 at 13:14
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Nov 8 '13 at 22:25
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ what will be the complexity of this solution? and also what will be the size of dag formed? $\endgroup$ – Daga Jan 20 '16 at 18:23
  • $\begingroup$ For this particular game you don't need the more general solution. For the more general solution, the complexity is polynomial in the size of the graph, which is the number of states in the game. $\endgroup$ – Yuval Filmus Jan 20 '16 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.