Take away games

1.2k Views Asked by At

Takeaway Game

Consider the takeaway game with the subtraction set $S = {1,4,5}$. Assuming there are two players and Player 1 moves first, if there are 87 tokens on the table, who wins with smart play?

I am familiar with the case of when the subtraction set is 1,2 or 3 tokens, ie. with 21 tokens in the case of a subtraction set $S= {1,2,3}$ the player who goes first will win but i dont know how to translate that to being able to take away different amounts of tokens.

1

There are 1 best solutions below

0
On

Start by working out who wins with best play for some smaller values. This is very easy to do once you realize that for each number $n$ of counters, you need only consider who wins when there are $n-1$, $n-4$, or $n-5$ counters. Specifically, if one of those values is a win for the second player, then you as the first player should leave that value for your opponent. For instance, $2$ counters is a win for the second player, so you can win playing first from $3,6$, or $7$ counters by leaving the other player $2$ counters.

$$\begin{array}{rcc} n:&\color{red}0&1&2&3&4&5&6&7&\color{red}8&9&10&11&12&13&14&15&\color{red}{16}&17&18\\ \text{wins}:&\color{red}2&1&2&1&1&1&1&1&\color{red}2&1&2&1&1&1&1&1&\color{red}2&1&2 \end{array}$$

I’ve carried this a little further than necessary to emphasize what’s happening. Notice the repetitions: the sequence of winners $1,1,2,1,1,1,1,1$ seems to be repeating.

  • Prove that it really is repeating with a period of $8$. Then use that to answer the question.

If you add a third line to the table showing the winning move(s) for the first player (in the positions in which the first player has one), you’ll see that it also repeats.