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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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

This question was marked as an exact duplicate of an existing question.

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|cite|improve this answer

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