Nim

Nim is a game played with heaps of stones, where two players take it in turn to remove any number of stones from any heap until no stones remain.
We’ll consider the three-heap normal-play version of Nim, which works as follows:
At the start of the game there are three heaps of stones.
On each player’s turn, the player may remove any positive number of stones from any single heap.
The first player unable to move (because no stones remain) loses.
If $(n_1,n_2,n_3)$ indicates a Nim position consisting of heaps of size $n_1$, $n_2$, and $n_3$, then there is a simple function, which you may look up or attempt to deduce for yourself, $X(n_1,n_2,n_3)$ that returns:
zero if, with perfect strategy, the player about to move will eventually lose; or
non-zero if, with perfect strategy, the player about to move will eventually win.
For example $X(1,2,3) = 0$ because, no matter what the current player does, the opponent can respond with a move that leaves two heaps of equal size, at which point every move by the current player can be mirrored by the opponent until no stones remain; so the current player loses. To illustrate:
current player moves to $(1,2,1)$
opponent moves to $(1,0,1)$
current player moves to $(0,0,1)$
opponent moves to $(0,0,0)$, and so wins.
For how many positive integers $n \le 2^{30}$ does $X(n,2n,3n) = 0$ ?

The function ‘X’ is the nim-sum function, which is the binary xor operation. In the problem that we are considering, we are asked to find all ‘n’ such that the nim-sum X(n, 2n, 3n) is zero for ‘n’ less than or equal to 2^30.

The first step is to represent ‘n’, ‘2n’, and ‘3n’ in binary. ‘n’ is represented as is in binary, ‘2n’ shifts all binary digits of ‘n’ one place to the left (equivalent to multiplying by 2), and ‘3n’ is the result of adding ‘n’ and ‘2n’ therefore having 2 binary digits set for each binary digit of ‘n’.

Once we have the binary representations, we use the xor operation on corresponding bits in the three numbers.

In the case of our problem where the nim-sum is zero, this means each bit must be set an even number of times in the binary representations of n, 2n and 3n. From the description of how each of these numbers is represented in binary, you can see that a bit in the binary representation of ‘n’ corresponds to a single bit set in ‘n’, two bits set in ‘2n’, and two bits set in ‘3n’. This means that a bit in ‘n’ can only contribute 1, 3, or 5 total bits across ‘n’, ‘2n’, and ‘3n’. To satisfy the requirement of having an even number of bits set, each bit in ‘n’ therefore corresponds to 0 or 4 total bits in the nim-sum.

This restriction obviously means that the allowed ‘n’ are less than 2^30 as requested. Therefore, the number of ‘n’ that satisfy X(n, 2n, 3n) = 0 is the number of integers expressible in binary with at most 30 bits, where each bit corresponds to 0 or 4 total set bits, which is 2^15.

More Answers: