In NIM Game you have n piles each contains ai (0≤i<n) stones, two players alternate turns in each turn a player may remove any positive number of stones from a single pile, the player who cannot make a move loses the game.

Here’s an example n = 1,a0 = 30

First player take 29 stones.

Second player take 1 stone.

First player loses (a0 = 0).

However First player could’ve won if he took 30 stones in the first turn.

Another example n = 2,a0 =3,a1 = 3.

First player take 3 stones from a0.

Second player take 3 stones from a1.

Try playing the game here Stone game reading the next part

If **both** players play **optimally** who will win the game?

We can easily find who will win the game by calculating the bitwise XOR of all pile sizes(NIM sum) if this number is zero then second player wins otherwise first player wins.

So why does this work ? You can spend sometime trying to get some intuition by applying this rule on games with N ≤ 2, however when n grows a mathematical proof works best.

Here’s **a sketch of a proof** (Note: ^ is the bitwise xor)

lets assume we have piles a0,a1,…,an we prove that if a0^a1^…^an = 0 then we are in a losing position, otherwise we are in a winning position.

we prove the following

- A-base case if all piles contain 0 stones then we are in a losing state (0 ^ 0 ^ .. ^ 0 = 0)
- B-being in a losing state means that any move we make will put the opponent in a winning state

proof:

first being in a losing state means

a0 ^ a1 ^ a2 … ^ an = 0

lets assume without the loss of generality that we picked pile a0 to make our move and removed k (0<k≤an) stones from it

we need to prove that

(a0 – k) ^ a1 ^ a2 … ^ an != 0

starting from

a0 ^ a1 ^ a2 … ^ an = 0 xor both sides by a0 ^ (a0 – k)

we get

(a0 – k) ^ a1 ^ a2 … ^ an = a0 ^ (a0 – k)

but a0 ^ (a0 – k) will always be non zero for positive values of k.

- C-being in a wining state means that there exists a move that will put the opponent in a losing state

proof:

assume that

a0 ^ a1 ^ a2 … ^ an = x

lets write x in binary, and look at the highest bit set there exists at least one pile that has that bit set assume without the loss of generality that this pile a0

we need to prove that there’s some POSITIVE k such that

(a0-k) ^ a1 ^ a2 … ^ an = 0

but (a0-k) ^ a1 ^ a2 … ^ an = x ^ a0 ^ (a0 – k)

thus we need to solve x ^ a0 ^ (a0 – k) = 0

xor both sides by a0 – k

we get

x ^ a0 = a0 – k which means

k = a0 – (x ^ a0) and with the assumption that a0 has the highest bit in x means that x ^ a0 is strictly less than a0 thus k is positive and we’re done.

using A,B,C we can use induction to obtain the complete proof.

**Useful links**

**Sample Problems**

Box Game (Not direct NIM but try to get an observation and prove it in a similar way)