# Winning single-pile, variable limits Nim [duplicate]

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?

-

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

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.