[Math] The Game of Nim

puzzlerecreational-mathematics

A position in Nim consists of some piles of coins. Two players alternate, with each move removing a portion of one pile. The winner is the player who takes the last coin.

Suppose that the starting piles have size $n_1,…,n_k$. Prove that Player 2 has a winning startegy if and only if for every $j$, an even number of $n_1,…,n_k$ have a $1$ in position $j$ in their binary representation. For example, when the sizes are $1,2,3$, the binary representation are $1, 10, 11,$ and the condition holds.

Best Answer

This is a well known result. Surely you can google up something, or failing that, go to a math library and read a solution from "Winning Ways I-II" by Berlekamp, Conway and Guy.

But I'm glad to hear that you want to work it out yourself. Here are a couple of hints. Call a position in the game of Nim balanced, if the sequence of numbers of remaining coins in the piles satisfies the condition "even number of 1s in any position", and call it unbalanced otherwise.

1) Show that if a player is given a balanced position, then any move s/he will make leaves an unbalanced position.

2) Show that if we are given an unbalanced position, there exists a move (at least one, possibly more) that will leave the other player with a balanced position.

3) Note that the desired all-zeros end position is balanced. Apply a little bit of recursive thinking (or induction, if you like).

Related Question