Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

marked as duplicate by joriki, Brian M. Scott, rschwieb, Noah Snyder, Arkamis Oct 26 '12 at 15:54

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1 Answer 1

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<L<2(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.

share|improve this answer

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