Nim Fractals

Tanya Khovanova Department of Mathematics MIT Cambridge, MA 02139 USA

                   tanyakh@yahoo.com

Joshua Xiong Acton-Boxborough Regional High School Acton, MA 01719 USA

                 joshxiong7@gmail.com

Abstract

We enumerate P-positions in the game of Nim in two different ways. In one series of sequences we enumerate them by the maximum number of counters in a pile. In another series of sequences we enumerate them by the total number of counters.

We show that the game of Nim can be viewed as a cellular automaton, where the total number of counters divided by 2 can be considered as a generation in which P-positions are born. We prove that the three-pile Nim sequence enumerated by the total number of counters is a famous toothpick sequence based on the Ulam-Warburton cellular automaton. We introduce 10 new sequences.

1 Introduction

The study of the game of Nim is fundamental to the field of combinatorial game theory. Nim is known as an impartial combinatorial game, a game in which each player has the same moves available at each point in the game and has a complete amount of information about the game and the potential moves. In addition, there is no randomness in the game (such as rolling dice).

Originally introduced by Charles Bouton in 1901 [4], Nim has played a role in many combinatorial games. The relationship between Nim and other impartial combinatorial games can be described with the Sprague-Grundy Theorem [5, 10], which states that all impartial games are equivalent to a Nim heap.

Although the game of Nim has been studied extensively [1, 3, 6, 8], in this paper, we invent new sequences related to enumeration of the P-positions of Nim.

In Section 2 we introduce the game of Nim as well as Bouton’s general formula for Ppositions. In Section 3 we define the sequences we want to count and provide examples for the games with one and two piles. One set of sequences is indexed by the maximum number of counters in a P-position and the other by the total number of counters. All of these sequences exhibit fractal-like behavior.

We continue with calculating formulae for the sequences indexed by the maximum number of counters in Section 4. We calculate the three-piles case in Section 4.1 and the four-piles case in Section 4.2. It can be noted that the calculation method is different for an odd and an even number of piles. But these sections provide enough background for a general formula in Section 4.3.

Then we turn our attention to the sequences indexed by the total number of counters in Section 5. We start with calculating the three-piles case in Section 5.1. We were motivated by the fractal-like patterns in this sequence to discover that this sequence describes an evolution of a particular cellular automaton. We explain in Section 5.2 how Nim can be viewed as an automaton. We extend the definitions to allow any impartial combinatorial game to be viewed as an automaton in Section 5.3. In Section 5.4 we define the Ulam-Warburton automaton, three branches of which correspond to Nim with three piles. We proceed to enumerating four piles in Section 5.5 and arbitrarily many piles in Section 5.6.

2 The game of Nim

In Nim, there are k piles of counters, with p_{i} counters in each pile. Two players alternate turns by taking some or all of the counters in a single pile. The player who takes the last counter (or equivalently, makes the last move) wins. We may denote the state or position of a game with an ordered tuple P = (p_{1}, p_{2}, …, p_{k}).

We begin by introducing some general definitions in game theory. Assuming that both players use an optimal strategy, there are two types of positions in a game such as Nim:

Definition 1. A P-position is a position in which the previous player will win (the one who just moved). An N-position is a position in which the next player will win (the one about to move).

We denote the set of P-positions as P, and the set of N-positions as N. Thus, any move from a P-position must be an N-position, and conversely, every N-position has at least one move that results in a P-position. This motivates the following theorem [1]:

Theorem 2. Suppose that the positions of a finite impartial game can be partitioned into disjoint sets A and B with the properties:

1. Every move of a position in A is to a position in B.

2. Every position in B has at least one move to a position in A.

3. The terminal positions are in A.

Then A = P and B = N.

By definition, the Nim position (0, 0, …, 0) will be a (terminal) P-position. Note that the general winning strategy is to move to a P-position if possible.

To explicitly give a formula for P-positions, we need the following definition:

Definition 3. The nim-sum of two non-negative integers x, y is their bit-wise XOR: x ⊕ y. Suppose that x = (b_{j} … b_{2}b_{1})_{2} and y = (c_{j} … c_{2}c_{1})_{2} in binary with leading zeroes as necessary, where j is the minimum number of digits sufficient for the binary representations of x and y. Then the nim-sum of x and y is (d_{j} … d_{2}d_{1})_{2}, where d_{i} = b_{i} + c_{i} (mod 2) for 1 ≤ i ≤ j.

The nim-sum is clearly associative and commutative, and 0 is the identity element. Further, x ⊕ y = x ⊕ z implies y = z. We can extend the concept of nim-sum to a position (p_{1}, p_{2}, …, p_{k}): it is simply p_{1} ⊕ p_{2} ⊕ ⋯ ⊕ p_{k}.

The following theorem [4] describes the set of P-positions in Nim.

Theorem 4 (Bouton, 1901). P is the set of positions in the game of Nim with nim-sum 0, and N is the complement.

From here, we can show that the last pile in a P-position is a function of the previous k − 1 piles.

Corollary 5. A position (p_{1}, …, p_{k−1}, p_{k}) is a P-position if and only if p_{k} = p_{1} ⊕ ⋯ ⊕ p_{k−1}.

3 Nim sequences

We would like to enumerate P-positions in the game of Nim. We assume that the number of piles, k, is fixed, which means that piles of zero are allowed. There are two natural ways to enumerate these P-positions.

In the first set of sequences, we want to count the number of P-positions where the number of counters in each pile is bounded by some number n. We call these sequences indexed-by-maximum.

• a_{k}(n) is the number of P-positions in the game of Nim with k piles such that each pile has no more than n counters.

• d_{k}(n) is the number of P-positions in the game of Nim with k piles such that the largest pile has exactly n counters.

Note that d_{k}(n) is the sequence of first differences of a_{k}(n), and a_{k}(n) is the sequence of partial sums of d_{k}(n).

Another natural way to enumerate P-positions is bounding the total number of counters in all the piles. Note that the total number of counters in a P-position is even. We call these sequences indexed-by-total.

• A_{k}(n) is the number of P-positions in the game of Nim with k piles such that the total number of counters is no more than 2n.

• D_{k}(n) is the number of P-positions in the game of Nim with k piles such that the total number of counters is exactly 2n.

Once again, note that D_{k}(n) is the sequence of first differences of A_{k}(n), and A_{k}(n) is the sequence of partial sums of D_{k}(n).

These sequences exhibit fractal-like behavior. The source of this behavior is the selfsimilarity in the set of P-positions. Consider the positions (p_{1}, p_{2}, p_{3}), (2^{k} + p_{1}, 2^{k} + p_{2}, p_{3}), (2^{k} + p_{1}, p_{2}, 2^{k} + p_{3}), and (p_{1}, 2^{k} + p_{2}, 2^{k} + p_{3}), where max(p_{1}, p_{2}, p_{3}) < 2^{k}. If one of these is a P-position then the other three are also P-positions.

In our proofs, we loosely use the term “pile” to refer to the number of counters in the pile.

3.1 Relationship between sequences

Let #(P) be the total number of counters in a P-position P = (p_{1}, p_{2}, …, p_{k}); that is, #(P) = ∑ p_{i}. We will refer to this as the total sum of the P-position. Further, let max(P) denote the largest pile of P; that is, max(P) = max{p_{i}}.

The sequences a_{k}(n) and A_{k}(n) can bound each other due to the following lemma:

Lemma 6. 2 max(P) ≤ #(P) ≤ k max(P).

Proof. The upper bound is obvious. To prove the lower bound, consider the place values of the ones in the binary representation of max(P). By Theorem 4, the nim-sum is 0, and the only way for this to occur is if the other piles collectively have ones in each of those place values. The lower bound then follows immediately since the sum of the numbers other than max(P) is at least max(P).

Corollary 7. a_{k}(⌊2n/k⌋) ≤ A_{k}(n) ≤ a_{k}(n).

Proof. The sequence A_{k}(n) enumerates P-positions with no more than 2n counters. These positions cannot have more than n counters in any pile by Lemma 6, so they all are included in the enumeration corresponding to a_{k}(n). Further, every position with a maximum pile of no more than 2n/k must have a total sum of less than 2n. Thus, P-positions that are counted by a_{k}(⌊2n/k⌋) are all included in the count of A_{k}(n).

In the sections below we provide recursive formulae for sequences a, d, A, and D. For indices of the form 2^{m} − 1 the formula for a_{k} is particularly simple.

Lemma 8. a_{k}(2^{m} − 1) = 2^{m(k−1)}.

Proof. There are 2^{m} choices for each of the first k − 1 piles, for a total of 2^{m(k−1)} choices. By Corollary 5, the last pile is uniquely determined, and since no pile is greater than 2^{m} − 1, which is the largest number that has m digits in binary, the last pile will also not be greater than 2^{m} − 1.

Together with Corollary 7, we can prove the following bound:

Corollary 9.

2^{(k−1)⌊log_{2}(⌊2n/k⌋+1)⌋} ≤ a_{k}(⌊2n/k⌋) ≤ A_{k}(n) ≤ a_{k}(n) ≤ 2^{(k−1)⌈log_{2}(n+1)⌉}.

3.2 One or two piles

If there is only one pile, there is only one P-position: (0). Thus, a_{1}(n) = A_{1}(n) = 1 for all n, which is sequence \underline{A000012} in the OEIS [7]. Correspondingly, d_{1}(0) = D_{1}(0) = 1 and d_{1}(n) = D_{1}(n) = 0 for n ≥ 1, which is sequence \underline{A000007}.

The P-positions for the game with two piles are described by the following lemma:

Lemma 10. A position P is a P-position if and only if P = (x, x) for a non-negative integer x.

This means that a_{2}(n) = A_{2}(n) = n + 1, which is sequence \underline{A000027} with an initial offset of 0. In addition, d_{2}(n) = D_{2}(n) = 1, which is sequence \underline{A000012}.

From here, the formulae for the sequences become cumbersome to express only in terms of n, so we define n = 2^{b} − 1 + c, where b = ⌊log_{2} n⌋, and 1 ≤ c = n + 1 − 2^{⌊log_{2} n⌋} ≤ 2^{b}. In other words, b is the number of digits in the binary representation of n, and c − 1 is n without its first digit.

4 Indexed-by-maximum sequences

4.1 Three piles

Consider the set of P-positions in Nim with three piles. We want to find a formula for the number of such P-positions P with max(P) = n.

Theorem 11. For n > 0, d_{3}(n) = 6c − 3.

Proof. There are three P-positions that are permutations of (n, n, 0). All other P-positions have exactly one pile with n counters. However, in order for the nim-sum to be 0, one of the other piles must be at least 2^{b}, and then the last pile is uniquely defined. There are 3 choices for which pile has n counters, 2 choices for the pile that is at least 2^{b}, and c − 1 choices for the number of counters in this pile. This results in a total of 3 + 6(c − 1) = 6c − 3 P-positions.

In other words, d_{3}(n) = 6(n + 1 − 2^{⌊log_{2} n⌋}) − 3. This is sequence \underline{A241717} in the OEIS [7]: 1, 3, 3, 9, 3, 9, 15, 21, 3, 9, 15, 21, 27, 33, 39, 45, 3, 9, . . ..

If we arrange the numbers into a triangle as follows, the fractal-like behavior of the sequence can be seen:

3,

3, 9,

3, 9, 15, 21,

3, 9, 15, 21, 27, 33, 39, 45,

3, 9, 15, 21, 27, 33, 39, 45, 51, 57, 63, 69, 75, 81, 87, 93,

⋮

The length of each line is a power of 2, and each line converges to \underline{A016945}—the sequence 6n + 3.

Theorem 12. For n > 0, a_{3}(n) = 2^{2b} + 3c^{2}.

Proof. This statement is true for n = 2^{b} − 1 by Lemma 8. Now we prove the statement for all n = 2^{b} − 1 + c. There are 2^{2b} P-positions such that all piles are less than 2^{b}. If one of the piles is at least 2^{b}, then exactly one other pile must also be at least 2^{b}. The leftover pile is uniquely defined and is less than 2^{b}. There are 3 ways to designate the two piles greater than or equal to 2^{b}, and c different choices for each of those two piles, so the total is 2^{2b} + 3c^{2} P-positions, as desired.

In other words, a_{3}(n) = 2^{2⌊log_{2} n⌋} + 3(n + 1 − 2^{⌊log_{2} n⌋})^{2}. This is sequence \underline{A236305} in the OEIS [7]: 1, 4, 7, 16, 19, 28, 43, 64, 67, 76, 91, 112, . . .. This sequence also displays fractal-like behavior, much like the previous sequence.

4.2 Four piles

When there are four piles, we cannot apply the argument used in Theorem 12 because there is a possibility that all four piles have more than 2^{b} − 1 counters, and we need to make sure that each of them does not exceed n. However, a slight modification of our argument shows that we can find a recursive formula:

Theorem 13. For n > 0, a_{4}(n) = 2^{3b} + 6c^{2}2^{b} + a_{4}(c − 1).

Proof. Suppose that all of the piles are not greater than 2^{b} − 1. Similar to the argument in Theorem 12, the first three piles that are not less than 2^{b} uniquely define a P-position where all the piles are not less than 2^{b}. There are 2^{3b} such positions.

In addition to that, we can have either 2 or 4 piles that are greater than or equal to 2^{b}. If there are 2 such piles, we can choose them in 6 different ways, and each of those piles can be any of c possible numbers. We can then choose another pile in 2^{b} ways, and the last pile will thus be fixed and less than 2^{b}. This accounts for the total of 6 · 2^{b}c^{2} ways. If there are 4 piles that are greater than 2^{b} − 1, we can remove 2^{b} counters from each pile without changing the nim-sum, thus reducing this situation to one when all piles are no greater than c − 1, which can be done in a_{4}(c − 1) ways.

The sequence a_{4}(n) is sequence \underline{A241522}: 1, 8, 21, 64, 89, 168, 301, 512, 561, 712, . . ..

Corollary 14. For n > 0, d_{4}(n) = (12c − 6)2^{b} + d_{4}(c − 1).

Proof. We can either use a similar argument as before or the fact that this sequence is the first difference sequence of the sequence above.

The sequence d_{4}(n) is sequence \underline{A241718}: 1, 7, 13, 43, 25, 79, 133, 211, 49, 151, 253, . . ..

4.3 Many piles

We will now prove a more general formula for a_{k}(n) based on the parity of k.

Theorem 15. If k is odd, a_{k}(n) = \frac{(2^{b} + c)^{k} + (2^{b} − c)^{k}}{2^{b+1}} , for n > 0.

Proof. Suppose that 2i of the piles are at least 2^{b}. There are \binom{k}{2i} ways to choose which

piles these are, and there are c choices for each of these 2i piles. Of the remaining k−2i piles, there are 2^{b} choices for the first k − 2i − 1 piles. The last pile will be uniquely determined

by Lemma 5, and its size will not exceed 2^{b}. Hence, we get a total of \binom{k}{2i}2^{b(k−2i−1)}c^{2i}

P-positions.

Since 2i can range from 0 to k − 1, we get the following formula:

a_{k}(n) = \binom{k}{0}2^{b(k−1)}c^{0} + \binom{k}{2}2^{b(k−3)}c^{2} + ⋯ + \binom{k}{k − 1}2^{0}c^{k−1}.

We multiply both sides of this equation by 2^{b}:

2^{b}a_{k}(n) = \binom{k}{0}2^{bk}c^{0} + \binom{k}{2}2^{b(k−2)}c^{2} + ⋯ + \binom{k}{k − 1}2^{b}c^{k−1}.

Since

(2^{b} ± c)^{k} = \binom{k}{0}2^{bk}c^{0} ± \binom{k}{1}2^{b(k−1)}c^{1} + \binom{k}{2}2^{b(k−2)}c^{2} ± ⋯,

we have that

2^{b}a_{k}(n) = \frac{(2^{b} + c)^{k} + (2^{b} − c)^{k}}{2}

and

a_{k}(n) = \frac{(2^{b} + c)^{k} + (2^{b} − c)^{k}}{2^{b+1}} ,

as desired.

Note that if k = 3, we get a_{3}(n) = 2^{2b} + 3c^{2} as expected. If k = 5, we get a_{5}(n) = 2^{4b} + 10 · 2^{2b}c^{2} + 5c^{4}. This is sequence \underline{A241523}: 1, 16, 61, 256, 421, 976, 2101, 4096, 4741, . . ..

We can calculate d_{k}(n) for odd k in a similar manner, or by subtracting consecutive terms:

Theorem 16. If k is odd,

d_{k}(n) = \frac{(2^{b} + c)^{k} + (2^{b} − c)^{k} − (2^{b} + c − 1)^{k} − (2^{b} − c + 1)^{k}}{2^{b+1}} .

For example, if k = 5, d_{5}(n) = 10 · 2^{2b}(2c − 1) + 20c^{3} − 30c^{2} + 20c − 5. This sequence is sequence \underline{A241731}: 1, 15, 45, 195, 165, 555, 1125, 1995, 645, . . ..

Theorem 17. If k is even, a_{k}(n) = \frac{(2^{b} + c)^{k} + (2^{b} − c)^{k} − 2c^{k}}{2^{b+1}} + a_{k}(c − 1), for n > 0.

Proof. We can use the same argument as above for all cases except for when all of the piles

are at least 2^{b}. So if we do not consider this case, there are \frac{(2^{b} + c)^{k} + (2^{b} − c)^{k} − 2c^{k}}{2^{b+1}} such

P-positions. Suppose, now, that all of the piles are at least 2^{b}. Note that if we subtract 2^{b} from each of these piles, the nim-sum will not be changed, and now each pile is no more than n − 2^{b} = c − 1, so there are a_{k}(c − 1) such P-positions. So our formula is

a_{k}(n) = \frac{(2^{b} + c)^{k} + (2^{b} − c)^{k} − 2c^{k}}{2^{b+1}} + a_{k}(c − 1).

We can calculate d_{k}(n) for even k in a similar manner:

Theorem 18. If k is even, d_{k}(n) equals

\frac{(2^{b} + c)^{k} + (2^{b} − c)^{k} − (2^{b} + c − 1)^{k} − (2^{b} − c + 1)^{k} − 2c^{k} + 2(c − 1)^{k}}{2^{b+1}} + d_{k}(c − 1).

5 Indexed-by-total

We will now fix the total number of counters as 2n. Let s_{2}(n) denote the binary weight of n; that is, the number of ones in the binary expansion of n.

5.1 Three piles

Theorem 19. D_{3}(n) = 3^{s_{2}(n)}.

Proof. Represent each pile as a sum of distinct powers of 2. Each power of two, 2^{i}, can be present in exactly two piles, or not present at all. That means if we sum all the piles we get that n is the sum of powers of two that are present in exactly two piles. For each power of two that is present in the binary representation of n we can chose in 3 ways in which piles they occur, for a total of 3^{s_{2}(n)} ways.

This sequence is sequence \underline{A048883}: 1, 3, 3, 9, 3, 9, 9, 27, 3, 9, 9, 27, 9, 27, 27, 81, 3, 9, . . .. Indexing starts as follows: D_{3}(0) = 1, and D_{3}(1) = 3. This sequence satisfies the following recursion: D_{3}(2n) = D_{3}(n) and D_{3}(2n + 1) = 3D_{3}(n).

We can see the fractal-like behavior of this sequence by considering a recursive definition: Start with the multiset S_{0} = {1}. Then form a new multiset S_{i+1} by concatenating the elements of S_{i} with the three times the elements of S_{i}, and repeat ad infinitum. For example, S_{2} = {1, 3, 3, 9}. We form S_{3} by concatenating the elements of the set {3, 9, 9, 27}.

The sequence A_{3}(n): partial sums of D_{3}(n) is also present in the database. It is sequence \underline{A130665}: 1, 4, 7, 16, 19, 28, 37, 64, 67, 76, 85, 112, 121, 148, 175, . . .. The sequence satisfies the recursion: A_{3}(2n) = 3A_{3}(n − 1) + A_{3}(n) and A_{3}(2n + 1) = 4A_{3}(n).

We calculated this sequence and discovered that it is in the database as the sequence describing the number of cells in three branches of the Ulam-Warburton cellular automaton (see Ulam [12], Singmaster [9], Stanley and Chapman [11], Wolfram [13]). It is amazing how the On-Line Encyclopedia of Integer Sequences makes it possible to connect different areas of mathematics.

5.2 Evolution of Nim

A natural question that arises is that if P-positions in Nim can be enumerated by cells in an automaton, can we find a bijection between P-positions of Nim and cells in the automaton? We provide the construction in this subsection.

Call a P-position P_{1} a parent of a P-position P_{2} if #(P_{1}) + 2 = #(P_{2}) and P_{1} differs from P_{2} in exactly two piles with the same index, by one counter in each. Correspondingly, if P_{1} is a parent of P_{2}, we call P_{2} a child of P_{1}. The following lemma connects the parent-child relationship to the game.

Lemma 20. A parent P_{1} can be achieved in a game from P-position P_{2}.

Proof. Suppose piles i and j have one fewer counter in P_{1} than in P_{2}. Then in the first move a player takes one counter from the i-th pile. In the next move the next player takes one counter from the j-th pile.

The zero position: (0, 0, …, 0) does not have a parent. But any other P-position has a parent that is described by the following lemma:

Lemma 21. Any non-zero P-position has a parent. Each parent can be achieved by subtracting 1 from piles i and j, where p_{i} and p_{j} are non-empty piles with the same number of zeros at the end of their binary representations.

Proof. The nim-sum of p_{i} and p_{j} should not change: p_{i} ⊕p_{j} = (p_{i} −1)⊕(p_{j} −1). This is only possible if p_{i} and p_{j} have the same number of zeros at the end of their binary representations since they have to regroup in the same number of places.

Corollary 22. If there are 3 piles, each non-zero P-position has exactly one parent.

Proof. Consider the rightmost 1 in the binary representations of p_{1}, p_{2} and p_{3}. This 1 must appear in exactly two of the representations, and so these numbers have the same number of zeroes at the end of their binary representation.

Similarly, we can also describe a child.

Lemma 23. Each child can be achieved by adding 1 to piles i and j, where p_{i} and p_{j} has the same number of ones at the end of their binary representation.

Proof. The nim-sum of p_{i} and p_{j} should not change: p_{i} ⊕p_{j} = (p_{i} +1)⊕(p_{j} +1). This is only possible if p_{i} and p_{j} have the same number of ones at the end of their binary representations since they have to regroup in the same number of places.

If we play the game with 3 piles each P-position has exactly 0, 1, or 3 children.

This way we get a cellular automaton. We start with a zero position and call it alive. At each step the children of the living positions are born. Children that are born at step n are called n-generation and D_{k}(n) enumerates them. Similarly, A_{k}(n) enumerates all the cells that are alive by the time n.

After we wrote this paper, we discovered that there is a well-known notion of a game position being born on day n [1, 8]. If a P-position is of generation n, then it is born on day n.

5.3 Evolution of an impartial combinatorial game

Note that we can describe an evolution of any impartial combinatorial game using the following definition. We assume that the players behave optimally. That is, if they can move to a P-position they will do so.

A P-position P_{1} is a parent of P_{2} if there exists an optimal game of maximal length in which P_{1} is achieved from P_{2} in exactly two moves.

If the longest game starting with P_{1} takes 2n moves, then n is the generation number of P_{1}. For Nim this definition coincides with the previous one because the longest game starting from a P-position with 2n counters cannot take more than 2n moves.

There is a standard algorithm for finding P-positions. Start with the terminal P-positions and assume they were found at step 0. Then proceed by induction. Denote the set of Ppositions found at steps up to i as P_{i}. Denote the positions that are one move away from P_{i} as N_{i}. Then the P-positions that do not belong to P_{i} and all moves from which belong to N_{i} are the P-positions from P_{i+1} \ P_{i}. Note that P_{i} ⊂ P_{i+1} and N_{i} ⊂ N_{i+1}.

Lemma 24. P-positions found at step i are born in generation i.

Proof. All optimal moves from N_{i} lead to P_{i}. All moves from P_{i} lead to N_{i−1}. Thus, if there is an optimal game where the P-position P_{1} is reached after P-position P_{2}, then P_{1} was found at an earlier step. That means an optimal game starting with P_{1} ∈ P_{i} can not take more than 2i steps.

Now suppose P_{1} ∈ P_{i} \ P_{i−1}. That means there exists a move from P_{1} to N_{i−1} \ N_{i−2}. Similarly, there exists a move from N_{i−1} to P_{i−1} \ P_{i−2}. That means there exists an optimal game from P_{1} that takes 2i moves, so P_{1} is born in generation i.

5.4 Ulam-Warburton cellular automaton

Now we will describe an automaton that produces the same sequences as P-positions in the game of Nim with three piles.

Consider points on an infinite square grid on the plane. Start with the point (0, 0) and forbid any growth in the south branch. That is, points with coordinates (x, y), where y < 0 and y ≤ −|x| are not allowed to be born. At each moment a child is born if it has exactly one alive neighbor horizontally or vertically. Note that this corresponds to three branches of the Ulam-Warburton automaton when any direction is allowed. Figure 1 shows 6 generations of the automaton. We can clearly see the fractal formed by this automaton. The dots represent cells, and the dots are connected if they form a parent-child pair. The starting cell is in the bottom center.

The description of points born in generation n is well-known [2, 9, 11, 12, 13]. Suppose n = ∑_{j=1}^{i} 2^{r_{j}} for distinct integers r_{1} > r_{2} > ⋯ > r_{i} ≥ 0. Then the points that are born in generation n have coordinates Σ_{j=1}^{i}2^{r_{j}}v_{j}, where v_{j} ∈ {(0, 1), (0, −1), (1, 0), (−1, 0)} and v_{j} ≠ −v_{j−1} for j > 1.

We can describe three branches of this automaton in the following manner: Start in any of three directions (N, E, W) and move 2^{r_{1}} steps, then either continue forward or turn 90 degrees and move 2^{r_{2}} steps, and so on.

Theorem 25. The evolution graph of the game of Nim with three piles is the same as three branches of the evolution graph of the Ulam-Warburton automaton.

Figure 1: Ulam-Warburton automaton without the South branch after 6 generations

Proof. Consider a P-position in the game of Nim with three piles: (p_{1}, p_{2}, p_{3}). If this Pposition was born on step n, it means p_{1} ⊕ p_{2} ⊕ p_{3} = 0 and p_{1} + p_{2} + p_{3} = 2n. Suppose that we decompose each p_{i} into distinct powers of 2. Then the powers of 2 that appear will be the r_{j}. Further, each r_{j} is present in exactly two out of three piles. Now let us describe the ancestors of this P-position. Start with the zero position, then chose pile i_{1} and i_{2} in which the power r_{1} is present. Add 1 to both piles, and continue adding 2^{r_{1}} times. Then move to the next power and so on.

Analogously, with respect to the graph of the cellular automaton, chose a legal direction for each pair of piles. Pick a direction corresponding to the largest power of 2 in n and make 2^{r_{1}} steps forward in this direction. Take the next power of 2. If it corresponds to the same two piles continue forward, otherwise turn 90 degrees either left or right depending on the new pair and move 2^{r_{2}} steps.

Now we want to make an explicit bijection between cells in the automaton and Ppositions. To start, we identify the P-position (0, 1, 1) with the point (−1, 0) and West direction, the P-position (1, 0, 1) with the point (0, 1) and East direction, and the P-position (1, 1, 0) with the point (1, 0) and North direction. Now we define turns:

• Left turn: changing direction from (0, 1, 1) to (1, 1, 0), from (1, 1, 0) to (1, 0, 1), and from (1, 0, 1) to (0, 1, 1)

• Right turn: changing direction from (0, 1, 1) to (1, 0, 1), from (1, 0, 1) to (1, 1, 0), and from (1, 1, 0) to (0, 1, 1).

Each cell in the automaton (correspondingly, P-position) has exactly one parent. The cell (P-position) is uniquely described by the path from the starting point (terminal position). We showed the bijection between the paths which establishes the bijection between the cells and the P-positions.

For example, consider the P-position (14, 11, 5), which can be decomposed into powers of 2: (8 + 4 + 2, 8 + 2 + 1, 4 + 1). This means that the evolution happens in the following way. Start with the P-position (0, 0, 0), then 8 generations are born in the direction (1, 1, 0) until the P-position (8, 8, 0) is reached. After that 4 generations are born in the direction (1, 0, 1) until the P-position (12, 8, 4) is reached. After that 2 generations are born in the direction (1, 1, 0) reaching (14, 10, 4), then the child is born in the direction (0, 1, 1) reaching the final destination (14, 11, 5). This corresponds to the following walk on the automaton: 8 steps to the right until the coordinates (8, 0), turn right, 4 more steps reaching (8, −4), turn left and make 2 more steps reaching (10, −4), then turn left again and make one step to get to (10, −3).

It is more natural to place the Nim evolution in 3D, but such a graph is more difficult to draw and to visualize; see Figure 2.

Figure 2: Nim evolution after 6 generations in 3D

5.5 Four piles

Let us move to four piles. Each P-position can be represented as four non-negative integers. The number of possible parents is 1, 2, or 6. We describe the possibilities by considering the binary representation of the four numbers:

• 1: if there is exactly one pair of binary numbers with the same number of zeros at the end,

• 2: if the binary numbers can be paired so that the number of zeros at the end is the same within each pair and different for different pairs,

• 6: all four binary numbers have the same number of zeros at the end.

Similarly, the number of possible children is 1, 2, or 6. Table 1 shows examples of P-positions with different numbers of parents and children.

1 child 2 children 6 children
1 parent (0,1,2,3) (0,0,1,1) (0,0,2,2)
2 parents (0,1,4,5) (1,1,2,2) (2,2,4,4)
6 parents (1,3,5,7) (1,1,3,3) (1,1,1,1)

Table 1: P-positions with different numbers of parents/children

Suppose the total number of counters is 2n. We computed the sequence D_{4}(n), which is sequence \underline{A237711}: 1, 6, 7, 36, 13, 42, 43, 216, 49, 78, 55, 252, 85, . . .. Sequence D_{4}(n) can be described recursively:

Lemma 26. D_{4}(0) = 1, D_{4}(1) = 6, D_{4}(2n + 1) = 6D_{4}(n) for n ≥ 0, and D_{4}(2n + 2) = D_{4}(n + 1) + D_{4}(n) for n ≥ 0.

Proof. As we discussed before, the total number of counters in a P-position is even. Moreover, given a position, each 1 in the binary representation of a pile has a matching 1 in the binary representation of another pile. Thus, the ones not in unit positions do not affect the total number of counters modulo 4. That means if #(P) = 4n + 2, there are exactly two odd piles, and, if #(P) = 4n + 4, the total number of odd piles is either 0 or 4.

Suppose #(P) = 4n + 2, so there are two odd piles. Consider the following operation: subtract one counter from both odd piles and then divide all piles by two. This operation is a map from P-positions with total sum 4n+2 to all P-positions with total sum 2n. This map is a surjection, and each pre-image has 6 elements because by doubling a P-position with total sum 2n and adding two counters in any pair of 4 piles, we can get from any P-position with sum 2n to 6 P-positions with total sum 4n + 2. Therefore, D_{4}(2n + 1) = 6D_{4}(n).

Similarly, suppose #(P) = 4n+4, so there are 0 or 4 odd piles. We can create a bijection between all P-positions with total sum 2n+2 and P-positions with all even piles by doubling the piles in the former P-position. Doubling all piles and adding one counter to each of the piles is a bijection between all P-positions with total sum 2n and P-positions with all odd piles. Therefore, D_{4}(2n + 2) = D_{4}(n + 1) + D_{4}(n).

The corresponding sequence of partial sums A_{4}(n) is sequence \underline{A237686}: 1, 7, 14, 50, 63, 105, 148, 364, 413, 491, 546, 798, 883, 1141, . . .. This sequence can also be described recursively:

Lemma 27. A_{4}(0) = 1, A_{4}(1) = 7, A_{4}(2n + 1) = 7A_{4}(n) + A_{4}(n − 1) for n ≥ 1, and A_{4}(2n + 2) = 7A_{4}(n) + A_{4}(n + 1) for n ≥ 1.

Proof. We use induction to prove this statement. We can see that the base cases hold via direct computation. Now assume that the recurrence relation holds for k ≤ 2n. By definition, A_{4}(2n + 1) = A_{4}(2n) + D_{4}(2n + 1). Using the inductive hypothesis, A_{4}(2n + 1) = 7A_{4}(n−1)+A_{4}(n)+6D_{4}(n) = A_{4}(n−1)+6(A_{4}(n−1)+D_{4}(n))+A_{4}(n) = 7A_{4}(n)+A_{4}(n−1).

Similarly, by definition: A_{4}(2n+2) = A_{4}(2n+1)+D_{4}(2n+2). Using the previous result, A_{4}(2n+2) = 7A_{4}(n)+A_{4}(n−1)+D_{4}(n)+D_{4}(n+1) = 7A_{4}(n)+A_{4}(n+1), which completes the induction.

5.6 Many piles

We now calculate these sequences for any number of piles. First, we compute the initial terms of D_{k}.

Lemma 28. D_{k}(0) = 1, D_{k}(1) = \binom{k}{2}.

Proof. It is easy to see that D_{k}(0) = 1 because this is just the position (0, …, 0). In the

case of D_{k}(1), we can choose two piles to have one counter each in \binom{k}{2} ways, and this is

the only way for this position to have a nim-sum of zero.

The following theorem provides a recursive formula for D_{k}(n).

Theorem 29. Assuming D_{k}(j) = 0 for negative j:

D_{k}(2n + 1) = \binom{k}{2}D_{k}(n) + \binom{k}{6}D_{k}(n − 1) + \binom{k}{10}D_{k}(n − 2) + …,

D_{k}(2n + 2) = \binom{k}{0}D_{k}(n + 1) + \binom{k}{4}D_{k}(n) + \binom{k}{8}D_{k}(n − 1) + …,

Proof. We exploit the fact that each P-position with only even piles and total sum 2m can be realized by doubling each pile in a corresponding P-position with total sum m, which means that there is a bijection between all P-positions and all P-positions with only even piles.

If the total number of counters is 4n + 2, then the number of odd piles could be 4i + 2, where 4i + 2 ≤ k. If there are 4i + 2 odd piles, then we can choose which piles are odd in

\binom{k}{4i + 2} ways. Then we can remove one counter from every odd pile and divide each pile

by 2. Using the bijection above, there will be \binom{k}{4i + 2}D_{k}(n − i) such P-positions for each

choice of i. The case 4n + 4 is similar.

For example, if k = 5, then, D_{5}(0) = 1, D_{5}(1) = 10, D_{5}(2n + 1) = 10D_{5}(n), and D_{5}(2n + 2) = D_{5}(n + 1) + 5D_{5}(n). This is sequence \underline{A238759}: 1, 10, 15, 100, 65, 150, 175, 1000, 565, . . ..

Similarly, we can prove a recursive formula for A_{k}(n).

Theorem 30.

A_{k}(2n+1) = (\binom{k}{2} + \binom{k}{0}) A_{k}(n)+(\binom{k}{6} + \binom{k}{4}) A_{k}(n−1)+(\binom{k}{10} + \binom{k}{8}) A_{k}(n−

2) + ⋯,

A_{k}(2n + 2) = \binom{k}{0}A_{k}(n + 1) + (\binom{k}{2} + \binom{k}{4}) A_{k}(n) + (\binom{k}{6} + \binom{k}{8}) A_{k}(n − 1) + ⋯,

Proof. We can show this by using the partial sums of D_{k}.

For example, if k = 5, then, A_{5}(0) = 1, A_{5}(1) = 11, A_{5}(2n + 1) = 11A_{5}(n) + 5A_{5}(n − 1), and A_{5}(2n + 2) = A_{5}(n + 1) + 15A_{5}(n). This is sequence \underline{A238147}: 1, 11, 26, 126, 191, 341, 516, 1516, 2081, . . ..

6 Acknowledgments

We are grateful to the MIT-PRIMES program for supporting this research. We are also grateful to the anonymous reviewer for providing many useful comments.

References

[1] M. H. Albert, R. J. Nowakowski, and D. Wolfe, Lessons in Play, A K Peters, 2007.

[2] D. Applegate, O. E. Pol, and N. J. A. Sloane, The toothpick sequence and other se-

quences from cellular automata, http://arxiv.org/pdf/1004.3036v2.pdf, 2010.

[3] E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for your Mathematical Plays, vol. 1, second edition, A K Peters, 2001.

[4] C. L. Bouton. Nim, a game with a complete mathematical theory. Ann. of Math., 3 (1901–1902), 35–39.

[5] P. M. Grundy, Mathematics and games, Eureka 2 (1939), 6–8; reprinted 27 (1964), 9–11.

[6] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, 1979.

[7] The On-Line Encyclopedia of Integer Sequences, published electronically at

http://oeis.org, 2014.

[8] A. Siegel. Combinatorial Game Theory, American Mathematical Society, 2013.

[9] D. Singmaster, On the cellular automaton of Ulam and Warburton, M500 Magazine of The Open University, 195 (2003), 2–7.

[10] R. P. Sprague, Über mathematische Kampfspiele [On mathematical war games], Tôhoku Math. Journal 41 (1935–1936), 438–444.

[11] R. P. Stanley (proposer) and R. J. Chapman (solver), A tree in the integer lattice, Problem 10360, Amer. Math. Monthly, 101 (1994), 76; 105 (1998), 769–771.

[12] S. M. Ulam, On some mathematical problems connected with patterns of growth of figures, Mathematical Problems in Biological Sciences, 14 (1962), 215–224.

[13] S. Wolfram, A New Kind of Science, Wolfram Media, 2002.

2010 Mathematics Subject Classification: Primary 91A46; 68Q80. Keywords: combinatorial games, Nim, P-position, cellular automaton.

(Concerned with sequences \underline{A000007}, \underline{A000012}, \underline{A000027}, \underline{A016945}, \underline{A048883}, \underline{A130665}, \underline{A236305}, \underline{A237686}, \underline{A237711}, \underline{A238147}, \underline{A238759}, \underline{A241522}, \underline{A241523}, \underline{A241717}, \underline{A241718}, and \underline{A241731}.)

Received May 22 2014; revised version received July 13 2014. Published in Journal of Integer Sequences, July 14 2014.

Return to Journal of Integer Sequences home page.