2
$\begingroup$

Possible Duplicate:
Winning strategy for a matchstick game

The rules of this variant of Nim are as follows: Starting at zero, each player counts up between 1-N numbers. The person that counts a number L loses. N and L are declared at the start of the game by one player, the other player chooses who goes first.

For example, a game where N=2, L=9 might go like this:

P1: 1, 2 P2: 3 P1: 4, 5 P2: 6, 7 P1: 8 

I'm trying to find an algorithm that can win the game for any value of N and L. So far, I've come up with the following.

c = current number     if going first:   while L-c > N:     count n numbers   once L-c <= N:     count (L-c) numbers 

Is there a better way of doing this?

1 Answers 1

0

First we need to show that it is possible for the computer to always win. We can do this, since for any value of N and L, there is an optimal strategy that will allow one of the players to always win. Hence, if the computer lets the person pick N and L it then decides whether to play first or second.

Now we have to show that there is an optimal strategy for one of the players, for any value of N & L. If $1 < L < N+2$ then it is easy to see that the first player wins because all they have to do is to count to $L-1$ and then they win. If $L = N+2$ then no matter what player one does in the first round, player two can then count to $L-1$ and win. But what if we have large $L$?

We can re-phrase the game, and instead of saying players take turns to count up to $N$ numbers, they take turns to take up to $N$ away from $L$ If we look at it this way, it is easy now to see that if $(N+1)+1 then player one wins, since in their first turn they can take $L-(N+2)$ away from $L$. From player two's point of view, their first turn is now the same as playing a new game where they go first, and $L = N+2$ which we have already shown means that they will lose.

You can now argue inductively or iteratively, whichever you prefer to show that player 1 can always win if $L$ is not congruent to 1 modulo $N+1$ and that player 2 can always otherwise, by reducing any game we are given to one we already know how to win.

Finally now we have shown that we can write such a program, we just need to write it! (as well as translate our new game of taking things off $L$ to counting up to it. Tell it to play first if player 1 will win and second if player 2 will win. At each step, tell it to count up to the highest number it can that is congruent to 1 mod $N+1$ and then, with a bit of thought, we can see from our earlier argument why this means it will always win.