Nim-game, how many winning moves?

Question

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.

Answer 1

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$.

Therefore, there are always an odd number of winning moves, and at most one such move in each pile.

Answer 2

Interesting question! How do you prove that you can rearrange the largest pile and always get the NS=0? And also then you know that is a least one winning move but could there maybe be more than one winning move?