# Nim-game, how many winning moves?

Let us assume that we play a nim-game (last person who draws a card, wins) and are in a position $$a_1, a_2$$ (sizes of piles). Assume that we have nim-sum (NS) $$a \neq 0$$.

1. How many moves are there?

2. How many winning moves are there from this position?

Question 1: Since the sizes of my piles are $$a_1,a_2$$, there should be a total of $$a_1+a_2$$ moves that I could make, correct?

Question 2: If I want to win, I need to be in a position where every time it's my turn, the NS $$\neq0$$. Then, I need to make sure that every move I make creates a situation where the other person always gets a NS $$=0$$. We know that if the other person gets a NS $$=0$$, then when it's my turn it will always be true that the NS $$\neq 0$$, and this loop will continue until I win.

But how many winning moves are there? To go from a NS $$\neq 0$$ to NS $$=0$$, one winning strategy is to always take the pile with the biggest size (we know that $$a_1\neq a_2$$ when NS $$\neq 0$$), and re-arrange it in a way such that NS $$=0$$, but I'm in a bind as to how many winning moves there are.

EDIT: See this link for an explanation of the game and what the nim-sum is.

• Ok, I think I get it... Since there are 2 piles, and you know that re-arranging the biggest pile in a particular way should give you a NS $=0$, there is always 1 winning move. This would also imply that the possibility to win with a random move is $\frac{1}{a_1+a_2}$. – armara Feb 22 at 13:37

There is only one winning move. I will use $$+_2$$ to indicate nim-addition. If we write the numbers in the piles in binary, then nim-addition is simply addition modulo $$2$$ in each bit, so that $$+_2$$ is associative and commutative. Say $$a_1+_2 a_2=x$$ Then $$(a_1 +_2 x)+_2 a_2 = a_1 +_2 (a_2+x) = x+_2 x = 0$$ so that we may nim-add $$x$$ to either pile to get to a winning position. However, such a move is legal only if it reduces the number of counters in the pile.
Say that the leading bit of $$x$$ occurs in position $$n$$. For bit positions to the left of $$n$$, $$a_1$$ and $$a_2$$ agree, and in bit position $$n$$ they differ. Say $$a_1$$ has a $$1$$ in this position, and $$a_2$$ has a $$0$$. Then $$a_2 +_2 x> a_2$$ so this is not a legal move, and $$a_1 +_2 x< a_1,$$ so this move is legal.
In the general case, where there may be $$m$$ piles, we see that there is a winning move in pile $$k$$ if and only if $$a_k$$ has a $$1$$ in bit position $$n$$, where the leading bit 0f $$a_1+_2a_2+_2\cdots+_2 a_m$$ is in position $$n$$.