Why is Nim solvable with the xor operator?

Question

In the game of Nim, played with two players, if you have $n$ stacks of stones (where you can take any number of stones from a single pile each turn), losing positions are ones where the xor of the stack sizes equals 0.

I don't quite understand why this xor rule necessarily follows or why it is true.

Answer 1

The key properties of xor are the following:

• If we have non-negative integers $a_1,a_2\dots a_n$ and we change exactly one of them then the xor always changes
• If we have non-negative integers $a_1,a_2\dots a_n$ and their xor is not $0$ then we can reduce exactly one of them, so that the xor of all of them is $0$.

Try to prove these two properties.

Having these two properties in mind it is clear that if you start your turn with a position $a_1,a_2\dots a_n$ in which the xor is $0$ you won't be able to win this turn (as the xor won't be $0$ at the end, since it will change).

On the other hand, if you start in a position in which the xor is not $0$, you can make it $0$.

So if I start with a position in which the xor is not $0$ I can always make my opponent start his turn in a non-winning position, and eventually win.

If I start in a position in which the xor is $0$ then I will have to leave my opponent with a winning position.

Answer 2

I will give you an inductive winning strategy for the second player if the xor is zero. For a game with no stones, the second player has already won. Otherwise, suppose player 1 removes $2^m\le a<2^{m+1}$ stones from some pile. Then there has to be a pile left with at least $2^m$, say $b$ stones. Then $a xor b<b$, so you can leave $a xor b$ stones on it. Thus, the xor in zero again for the next turn of player 1. As the game is finite, player 2 will win using this strategy. For the case that the xor at the beginning is some $x>0$, the situation is equivalent to a game with $n+1$ piles, where the last pile had $x$ stones, and the "second" player begun by removing it.