Problem 301: Nim

Detailed mathematical approach

Problem Summary

Nim is played with heaps of stones: two players move alternately, a move takes any positive number of stones from one single heap, and the player who cannot move, because no stones are left, loses. In the three-heap version \((n_1,n_2,n_3)\) denotes heaps of \(n_1\), \(n_2\) and \(n_3\) stones, and the statement calls \(X(n_1,n_2,n_3)\) a simple function that is zero when the player about to move loses under perfect play and non-zero otherwise. Its example is \(X(1,2,3)=0\), argued by mirroring: every move can be answered by one leaving two equal heaps, and the opponent then copies every move. We must count the positive integers \(n\le2^{30}\) with \(X(n,2n,3n)=0\). ^[1]

The whole solution in one sentence: the triple \((n,2n,3n)\) is losing for the player to move exactly when the binary digits of \(n\) contain no two neighbouring ones, and the number of such \(n\) up to \(2^k\) is a single Fibonacci number.

Mathematical Approach

We prove that \(X=0\) means that the bitwise exclusive-or of the heap sizes is \(0\), turn \(n\oplus2n\oplus3n=0\) into a condition on the binary digits of \(n\) alone, and count the admissible digit patterns.

1. The nim-sum

Let \(a\oplus b\) be the bitwise exclusive-or: add the binary digits of \(a\) and \(b\) in each place separately and drop every carry, so that \(1\oplus1=0\). ^[3] The nim-sum of a position is

$$s(n_1,n_2,n_3)=n_1\oplus n_2\oplus n_3.$$

In the example of the statement \(1\oplus2=11_2=3\) and \(3\oplus3=0\), so \(s(1,2,3)=0\).

2. Why the nim-sum decides the game

Theorem (Bouton, 1901–1902). The player about to move loses under perfect play if and only if the nim-sum of the position is \(0\). ^[2]

For contrast, \((1,2,4)\) has nim-sum \(1\oplus2\oplus4=7\): replacing the heap of \(4\) by \(4\oplus7=3\) removes one stone and leaves the losing position \((1,2,3)\). The proof turns that trick into a rule. A move replaces a heap of size \(h\) by one of size \(h'\) with \(0\le h'\lt h\); the untouched heaps cancel in the exclusive-or, so the new nim-sum is \(s\oplus h\oplus h'\), and two observations follow.

• If \(s=0\), every move leaves \(h\oplus h'\ne0\), because \(h\ne h'\).
• If \(s\ne0\), some move reaches \(0\). Let \(d\) be the highest place where \(s\) has digit \(1\); some heap \(h\) has digit \(1\) there, else that digit of \(s\) would be \(0\). Put \(h'=h\oplus s\). Above \(d\) the digits of \(s\) vanish, so \(h\) and \(h'\) agree there, while at \(d\) the digit \(1\) of \(h\) becomes \(0\); hence \(h'\lt h\), removing \(h-h'\) stones is legal, and the new nim-sum is \(s\oplus h\oplus(h\oplus s)=0\).

Induct on the total number of stones, which strictly decreases at every move. With no stones left the player to move loses and \(s=0\). Otherwise a zero nim-sum hands the opponent a non-zero one, which the opponent wins by induction, so the position is lost; a non-zero nim-sum admits a move to \(0\), which the opponent loses, so the position is won. Hence \(X(n_1,n_2,n_3)=0\) exactly when \(s=0\), which is all the count needs.

3. Addition, exclusive-or and carries

Let \(a\wedge b\) be the bitwise and: digit \(1\) exactly where both numbers have digit \(1\). ^[3] For all non-negative integers,

$$a+b=(a\oplus b)+2\,(a\wedge b).$$

Write \(a=\sum_i a_i2^i\) and \(b=\sum_i b_i2^i\) with digits in \(\{0,1\}\). In one place the four cases \(0+0=0\), \(0+1=1\), \(1+0=1\) and \(1+1=2\) say exactly that

$$a_i+b_i=(a_i\oplus b_i)+2(a_i\wedge b_i),$$

and multiplying by \(2^i\) and summing gives the identity, since \(\oplus\) and \(\wedge\) act place by place. The carry correction \(2(a\wedge b)\) vanishes only for \(a\wedge b=0\), so

$$a\oplus b=a+b\iff a\wedge b=0.$$

4. From the game to the digits

By Section 2 we must count the \(n\) with \(n\oplus2n\oplus3n=0\). Since \(x\oplus y=0\) means \(x=y\), this says \(n\oplus2n=3n\); and \(3n=n+2n\), so Section 3 turns the equation into

$$n\wedge2n=0.$$

Nothing about Nim is left.

5. No two neighbouring ones

Doubling shifts the binary digits one place to the left, ^[3] so digit \(i\) of \(2n\) is digit \(i-1\) of \(n\), and digit \(0\) of \(2n\) is \(0\). Hence digit \(i\) of \(n\wedge2n\) is \(1\) exactly when \(n\) has digit \(1\) in both places \(i\) and \(i-1\), and \(n\wedge2n=0\) holds if and only if the binary expansion of \(n\) avoids the block \(11\). Such integers are called fibbinary numbers. ^[5]

For \(n=5=101_2\) the expansion has no neighbouring pair, and indeed \(5\oplus10\oplus15=0\). For \(n=6=110_2\) it has one: \(6\wedge12=4\), the addition \(6+12\) carries, and \(6\oplus12\oplus18=24\ne0\).

6. Counting digit strings that avoid the block

With three binary places the admissible strings are \(000\), \(001\), \(010\), \(100\), \(101\): the three ending in \(0\) come from appending \(0\) to \(00\), \(01\), \(10\), and the two ending in \(1\) come from appending \(01\) to \(0\) and \(1\). So \(5=3+2\), and that split works in general.

Fix \(k\ge0\). The integers \(0\le n\lt2^k\) are exactly the strings \(b_{k-1}\dots b_0\) of \(k\) binary digits with leading zeros allowed, and a leading zero never creates a neighbouring pair. Let \(A_t\) count the strings of length \(t\) that avoid \(11\), so \(A_0=1\) for the empty string and \(A_1=2\). For \(t\ge2\) split on the last digit: if \(b_0=0\) then \(b_{t-1}\dots b_1\) is an arbitrary admissible string of length \(t-1\); if \(b_0=1\) then \(b_1=0\) is forced and \(b_{t-1}\dots b_2\) is one of length \(t-2\). Both descriptions are reversible and the cases are disjoint, so

$$A_t=A_{t-1}+A_{t-2}\qquad(t\ge2),$$

the Fibonacci recurrence. ^[4] With \(F_0=0\) and \(F_1=1\) we have \(A_0=F_2\) and \(A_1=F_3\), so induction gives \(A_t=F_{t+2}\); the first values are \(1,2,3,5,8,13,21\). The count also follows from Zeckendorf's theorem: ^[6] avoiding the block \(11\) avoids two consecutive Fibonacci indices, so \(b_{k-1}\dots b_0\mapsto\sum_i b_iF_{i+2}\) is injective on the admissible strings; its values reach at most \(F_{k+1}+F_{k-1}+\dots=F_{k+2}-1\), and an integer below \(F_{k+2}\) cannot use an index above \(k+1\), so each of those values occurs.

7. The range the problem asks about

The count \(A_k=F_{k+2}\) belongs to \(0\le n\lt2^k\), while the problem asks for \(1\le n\le2^k\). The two sets differ in two numbers: we lose \(n=0\), which has no digit \(1\) at all, and we gain \(n=2^k\), a single one followed by \(k\) zeros. Both are admissible, so one admissible number leaves and one enters and the count is unchanged:

$$\#\{\,1\le n\le2^k: X(n,2n,3n)=0\,\}=F_{k+2}.$$

The boundary deserves care. Over \(1\le n\lt2^k\) the count drops to \(F_{k+2}-1\), for \(k=4\) seven instead of eight, and counting strings of length \(k+1\) would give \(F_{k+3}\), one Fibonacci step too large.

8. A worked example and the checkpoints

Take \(k=4\), so \(1\le n\le16\). The admissible values are \(1,2,4,5,8,9,10,16\), in binary \(1\), \(10\), \(100\), \(101\), \(1000\), \(1001\), \(1010\) and \(10000\); each of the other eight numbers, \(3,6,7,11,12,13,14,15\), contains the block \(11\). The count is \(8=F_6\), as the formula promises. Likewise \(k=3\) admits \(1,2,4,5,8\) and gives \(5=F_5\), while \(k=10\) gives \(F_{12}=144\), \(k=16\) gives \(F_{18}=2584\) and \(k=22\) gives \(F_{24}=46368\). The value \(n=1\) is the position \((1,2,3)\) of the statement, and it is counted.

How the Code Works

All three solve routines evaluate the formula of Section 7 without ever looking at an individual \(n\); only the C++ checkpoints, which run by default, enumerate values. In the C++ file ^[7] parse_arguments fills an Options record from --exponent= followed by digits, which parse_int_after_prefix converts, and from --skip-checkpoints; the defaults are the exponent \(30\) with checkpoints on, and only exponents between \(1\) and \(60\) are admitted.

solve is the whole method. It sets bits to exponent + 1, allocates a vector fib of bits + 2 zeros, sets fib[1] = 1, fills fib[i] = fib[i-1] + fib[i-2] up to the index bits + 1 and returns that entry. Then fib[i] is \(F_i\) for \(F_0=0\), \(F_1=1\), and the returned index is the exponent plus two, so the value is the \(F_{k+2}\) of Section 7. The name bits counts the binary places of an integer up to \(2^k\), one less than the index used.

brute_small is the slow counterpart: it walks over every \(n\) with \(1\le n\le2^k\) and counts those with (n ^ (2*n) ^ (3*n)) == 0, the condition of Section 4 in C++ operators. run_checkpoints compares the two at the exponents \(3\) and \(10\); on a mismatch it names the failing one and main stops with exit code \(2\), otherwise main prints solve(options.exponent).

The Python file is the same solve with exponent=30 as a default argument, a list in place of the vector and no checkpoints; the Java class fixes the exponent at \(30\) and uses a long[]. C++ accumulates in std::uint64_t, an exactly \(64\)-bit type where it is defined, and its ceiling of \(60\) keeps the largest entry at \(F_{62}=4052739537881\), far below \(F_{94}\), the first Fibonacci number too large for an unsigned \(64\)-bit counter; Java's signed long reaches \(F_{92}\), and Python's integers have no fixed width. ^[8]

Complexity and Verification

solve performs \(k+1\) additions and stores \(k+3\) integers. With one machine-word addition as the unit step that is \(O(k)\) time and \(O(k)\) memory, and two rolling variables would cut the memory to \(O(1)\); with unbounded integers the entries have \(\Theta(k)\) binary digits, so the additions cost \(\Theta(k^2)\) digit operations. A direct count is \(O(2^k)\) instead, more than a thousand million candidates at \(k=30\), so brute_small runs only at the exponents \(3\) and \(10\).

By Binet's formula \(F_m=(\varphi^m-\psi^m)/\sqrt5\), with \(\varphi=(1+\sqrt5)/2\) and \(\psi=(1-\sqrt5)/2\), ^[4] the second power is negligible because \(|\psi|\lt1\), so the share \(F_{k+2}/2^k\) of admissible integers is asymptotic to \((\varphi^2/\sqrt5)(\varphi/2)^k\) and tends to \(0\) because \(\varphi\lt2\): measured, it falls from \(144/2^{10}\approx0.1406\) to \(46368/2^{22}\approx0.0111\).

The reasoning was also verified for this article with separate programs.

• A retrograde analysis of all \(1000\) three-heap positions with heaps of at most \(9\) stones marks a position as lost exactly when its nim-sum is \(0\), confirming Section 2.
• Solving the game itself for \((n,2n,3n)\) with \(n\le12\), up to \(12025\) positions per value, gives the losing values \(1,2,4,5,8,9,10\): exactly the \(n\) there with no neighbouring pair of ones.
• The identity of Section 3 holds for all pairs \(a,b\lt256\), and the conditions \(n\oplus2n\oplus3n=0\), \(n\wedge2n=0\) and the absence of the block \(11\) agree for every \(n\lt2^{20}\).
• A direct count over \(1\le n\le2^k\) equals \(F_{k+2}\) for every \(k\le22\); a two-state count over the digits reproduces it, and the Zeckendorf map of Section 6 was confirmed one to one onto \(\{0,\dots,F_{k+2}-1\}\) for \(k\le20\).
• At the exponents \(1\), \(2\), \(3\), \(10\), \(16\) and \(22\) the three programs all return \(2\), \(3\), \(5\), \(144\), \(2584\) and \(46368\): the unchanged C++ through --exponent=, the unchanged Python through the argument of solve, and Java through a temporary copy whose fixed exponent was made adjustable.

The C++ parser has one flaw, which the intended runs never reach: parse_int_after_prefix accumulates digits into a signed int without checking the running value, so with a 32-bit int the argument --exponent=2147483648 already overflows it, which is undefined behaviour, before the range test can reject the value. Exponents in the supported range \(1\) to \(60\) are unaffected.

Footnotes and References

The references below supply the background facts used above; the Nim proof, the reduction to a digit condition and the counting recurrence are derived explicitly here.

1. Project Euler 301 — Nim. The official statement describes three-heap Nim under the normal-play rule, defines X(n₁, n₂, n₃) to be zero exactly when the player about to move loses under perfect play, gives X(1, 2, 3) = 0, and asks how many positive integers n ≤ 2³⁰ satisfy X(n, 2n, 3n) = 0.
2. Wikipedia — Nim. It defines the nim-sum as the binary digital sum of the heap sizes without carries, the bitwise exclusive-or, and states the theorem of Section 2: the player to move wins under perfect play if and only if the nim-sum is not zero. It attributes the proof to C. Bouton, Annals of Mathematics, second series, volume 3, 1901–1902.
3. Wikipedia — Bitwise operation. Exclusive-or gives 1 where exactly one operand has a 1, the bitwise and gives 1 only where both have a 1, and a left shift by n multiplies by 2ⁿ when nothing overflows — for n = 1 the doubling of Section 5.
4. Wikipedia — Fibonacci sequence. It fixes the convention F₀ = 0, F₁ = 1, Fₙ = Fₙ₋₁ + Fₙ₋₂ used here, lists the first terms 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …, and gives Binet's formula with both of its roots.
5. OEIS A003714 — fibbinary numbers. The sequence lists the integers whose binary representation contains no two adjacent 1s: 0, 1, 2, 4, 5, 8, 9, 10, 16, 17, 18, … Its entry defines the n-th term by reading the Zeckendorf digits of n as a binary integer, the inverse of the map in Section 6, and notes that the count below a power of two is a Fibonacci number.
6. Wikipedia — Zeckendorf's theorem. Every positive integer has exactly one representation as a sum of distinct Fibonacci numbers no two of which are consecutive, all indices being at least 2; the example given is 64 = 55 + 8 + 1.
7. C++ — Euler301.cpp. The linked immutable C++ revision contains parse_arguments, solve, brute_small and run_checkpoints, and is the implementation record for this article.
8. cppreference — fixed width integer types records that std::uint64_t is optional but, where defined, is unsigned with exactly 64 bits; Java — Long gives the signed 64-bit range −2⁶³ to 2⁶³ − 1, and Python — numeric types states that integers have unlimited precision.