Original description from the Project Euler:

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\) ?

Solution:

To solve the problem, we first need to define state S: Write the number of stones in each heap in binary. If the number of each digit adds up to 0 or 2, we called this is state S. For example, \((1,2,3)\) is in S because their binary forms are

and they sum up to \(2 2\). Moreover, \((0,0,0)\) is also in S. For another example, \((3,6,9)\) is not in state S, because

and they sum up to \(1 1 2 2\).

According to Bouton (1901-1902), (i) All states S will be diminished if we move any rocks from one heap. This is because, given the number of rocks in the other two heaps, the number that establishes S is unique. (ii) If S is diminished in the first step, it can always be re-established in the next step.

Following these two theorems, we can show that if one player starts with S, he or she has to diminish it in the move and his or her opponent should always re-established S in the next step by “perfect strategy”. Therefore, the player will always start his or her move with S, and the number of rocks in heaps will eventually go to \((0,0,0)\). Namely, the player starts with \((0,0,0)\) and loses. Otherwise, if one player starts with a non-S state, he or she should establish S in his or her movement, and his or her opponent will always start the game with S and eventually lose.

We may check how many positive integers \(n \le 2^{30}\) would initially establish S. However, it can be computationally hard. By observation of the number combination of \((n,2n,3n)\), we can identify that if we have in its binary form \(2n\) equals to adding one 0 at the of \(n\). For example, \(3 = 0 0 1 1\) and \(6 = 0 1 1 0\). Note that if we add a 0 at the end of 3, it becomes 6. Therefore, if we want the same digits in the three numbers add up to 0 or 2, the digits in \(n\) have to be \(\cdots 0 \cdots\) or \(\cdots 01 \cdots\). The corresponding digits in \(2n\) are \(\cdots 0 \cdots\) or \(\cdots 10 \cdots\), and the corresponding digits in \(3n\) are \(\cdots 0 \cdots\) or \(\cdots 11 \cdots\).

Therefore, we can use either \(\cdots 0 \cdots\) or \(\cdots 10 \cdots\) to fill the 31 digits of the \(2^{30}\). As the three piles of rock contain n, 2n, 3n rock, we must obeserve 11 10 01 sequence or sequesetive 0s. Supposing we have \(f(a)\) methods to fill for \(a\) digits, we have \(f(a) = f(a-1) + f(a-2)\). Thus, this problem becomes to solve \(f(31)\), excluding \(n = 0\) but including \(n = 2^{30}\).

Source code in Python:

def f(n):
    """This function is designed to solve Nim problem (problem 301) in the ProjectEuler.
    Args:
        n: related to the indicator to 2 given in the problem. n = indicator + 1
    Return:
        return the number of positive integers that always makes the first player to 
        lose the game.
    """
    if n == 1: return 1 
    elif n == 2: return 2
    else: return f(n-1)+f(n-2)

print(f(31) - 1 + 1) #2178309, -1 for excluding 0, +1 for including 2^30

Reference:

Project Euler. Nim. https://projecteuler.net/problem=301.

Charles L. Bouton. Nim, A Game with a Complete Mathematical Theory. Annals of Mathematics, Second Series, Vol. 3, No. 1/4 (1901 - 1902), pp. 35-39.