Global Fibonacci nim

Abstract

Fibonacci nim is a popular impartial combinatorial game, usually played with a single pile of stones: two players alternate in removing no more than twice the previous player’s removal. The game is appealing due to its surprising connections with the Fibonacci numbers and the Zeckendorf representation. In this article, we investigate some properties of a variant played with multiple piles of stones, and solve the 2-pile case. A player chooses one of the piles and plays as in Fibonacci nim, but here the move-size restriction is a global parameter, valid for any pile.

1 Introduction

The classical game of Fibonacci nim, as studied by Whinihan in (1963), is played as follows: There is one pile of stones, with n stones in the pile initially, and there are two players who take turns making moves. A move consists of removing some of the stones in the pile, subject to the following constraints: the first player must remove at least 1 stone, but may not remove the entire pile. On subsequent turns, if the previous player removed m stones, then the next player must remove at least one stone and at most 2 m stones. The loser is the player who is unable to make a move (usually because there are no stones remaining, although there is also a special case in which the initial pile has one stone).

In his original paper on the game, Whinihan described the outcome of the game under optimal play:

Theorem 1

(Whinihan 1963) The first player has a winning strategy if and only if n is not a Fibonacci number.

Furthermore, Whinihan gave a full winning strategy. This strategy relies on a celebrated theorem of Zeckendorf. However, it is also possible to give an alternative description of the winning strategy, in terms of partial sums of the so-called Fibonacci word. We introduce this word in Sect. 4 and deduce the winning strategy in terms of the Fibonacci word in Sect. 5.

It is natural to consider the game of Fibonacci nim played with more than one pile. In this game, one may remove stones from only one pile on any given move. However, there are two natural possibilities for the bound on the number of stones that may be removed:

• Local move dynamic Each pile has a separate counter, so that if the last move (by either player) in a pile was to remove m stones, then the next move in that pile must be to remove at most 2 m stones.

• Global move dynamic There is only one counter for the entire game, so that if the previous move was to remove m stones in any pile, then the next move must be to remove at most 2 m stones in any pile (either the same pile, or a different pile).

In either case, it is natural to remove the restriction that the first player may not remove an entire pile; this artificial rule is necessary to make the one-pile game nontrivial, but it serves no further purpose in either multi-pile game.

The local move dynamic game is more natural from the perspective of combinatorial game theory, as the game is the disjunctive sum of the individual piles. As a result, the game can be studied by means of the Sprague-Grundy theory (see Grundy 1939; Sprague 1935); the authors have previously analyzed this version in Larsson and Rubinstein-Salzedo (2016).

The global move dynamic game is probably the more natural one from the perspective of game play, and it must be analyzed differently, as the powerful tools based on Grundy values and disjunctive sums are not applicable. In Sect. 6 we give the outcome class for all two-pile positions, first in terms of Zeckendorf representation, and then in terms of a generalized version of the Fibonacci word. (See also Larsson (2009) for another move dynamic game on two piles with a similar solution). In Sect. 7 we study some properties of positions with several piles. Finally, in Sect. 8, we describe a simpler variant of the global move dynamic game, in which we can describe the full winning strategy.

We use the notation $(n_1,\ldots ,n_k;r)$ to denote the global Fibonacci nim position with piles of size $n_1,\ldots ,n_k$, where the maximum number of stones that can be removed on the first turn is r. We write $(n_1,\ldots ,n_k;\infty )$ for the global Fibonacci nim position with piles of size $n_1,\ldots ,n_k$, where any number of stones can be removed on the first turn, provided that they are all from the same pile.

Throughout the paper, we write $F_n$ for the nth Fibonacci number, indexed so that $F_0=0$ and $F_1=1$. We will frequently need to refer to the index of a certain Fibonacci number, i.e. if n is a Fibonacci number, the value of k such that $F_k=n$. This is ambiguous in the case of 1, since $F_1=F_2=1$. When we refer to the index of 1, we always mean 2, rather than 1.

2 ${\mathcal {N}}$ and ${\mathcal {P}}$ positions

Definition 2

We say that a game G is an ${\mathcal {N}}$ position (resp. ${\mathcal {P}}$ position) and write $G\in {\mathcal {N}}$ (resp. $G\in {\mathcal {P}}$) if the player to move (resp. player not to move) has a winning strategy under optimal play.

Given an impartial game (i.e. one in which both players have the same moves available to them, as opposed to e.g. chess, where one player moves the white pieces and one player moves the black pieces), there is a simple recursive characterization of the ${\mathcal {N}}$ and ${\mathcal {P}}$ positions.

Proposition 3

$G\in {\mathcal {N}}$ if and only if there exists a move to a game $G'$ such that $G'\in {\mathcal {P}}$.

See Albert et al. (2007, Theorem 2.13).

Consequently, $G\in {\mathcal {P}}$ if and only if, for every move to a game $G'$, we have $G'\in {\mathcal {N}}$.

3 Zeckendorf representation

A celebrated theorem of Lekkerkerker and Zeckendorf is the following:

Theorem 4

(Lekkerkerker 1952; Zeckendorf 1972) Every positive integer n can be expressed uniquely as a sum of pairwise nonconsecutive Fibonacci numbers with index at least 2.

Definition 5

The Zeckendorf representation of n is the unique sequence $z_1(n),z_2(n),\ldots ,z_k(n)$ of Fibonacci numbers, with index greater than 1, such that $z_1(n)+\cdots +z_k(n)=n$, and for all $1\leqslant i<k$, $z_i(n)<z_{i+1}(n)$, and $z_i(n)$ and $z_{i+1}(n)$ are not consecutive elements of the Fibonacci sequence. We write ${\mathcal {Z}}(n)=\{z_1(n),\ldots ,z_k(n)\}$.

For notational convenience, if $|{\mathcal {Z}}(n)|<k$, then we set $z_k(n)=\infty$, and we say that $z_k(n)>m$ for all integers m. Extending this convention to 0, we also set $z_k(0)=\infty$ for all k.

4 The Fibonacci word

The Fibonacci word $W^{x,y} = f_0f_1f_2\ldots$ is a string of digits from some two-letter alphabet $\{x,y\}$. It is an archetype of a so-called Sturmian word; see Lothaire (2012) for much more on Sturmian words. There are many equivalent ways of generating it.

Proposition 6

The following constructions give rise to the same sequence $f_0f_1f_2\ldots$:

• (1) Let $S_0=x$ and $S_1=xy$. For $n\geqslant 2$, let $S_n=S_{n-1}S_{n-2}$ be the concatenation of strings. Then, for every n, $S_n$ is an initial string of $S_{n+1}$. The Fibonacci word $S_\infty$ is the limiting string of the sequence $\{S_0,S_1,S_2,\ldots \}$.

• (2) The Fibonacci word is the string $f_0f_1f_2\ldots$, where $f_n=x$ if $1\not \in {\mathcal {Z}}(n)$ and $f_n=y$ if $1\in {\mathcal {Z}}(n)$.

• (3) For an alphabet A, let $A^*$ denote the set of words on A. Then the Fibonacci word is the unique non-trivial word u on the alphabet (x, y) where the parallel update $\tau (x) = yz, \tau (y) = y$, $\tau : \{x,y\}\rightarrow \{y,z\}^*$ for all letters in u, gives back the same word, but now on the alphabet (y, z).

See (Jean 1986, p. 20) or Knuth (1987) for more details on the Fibonacci word, including a proof of Proposition 6, as well as other descriptions and interesting properties. The beginning of the Fibonacci word is

$$\begin{aligned} x y x x y x y x x y x x y x y x x y x y x x y x x y x y x x y x x y. \end{aligned}$$

In the following, we make use of partial sums of the Fibonacci word, after substituting certain integers for x and y, in particular when $x=F_{i+1}$ and $y=F_i$ for some i. For instance, if we substitute $x=8$ and $y=5$, and among the first $m+1$ letters (i.e. those indexed from 0 to m), there are i x’s and $j=m+1-i$ y’s, then the partial sum is $8i+5j$. We write $W_i^{8,5}$, when we refer to the ith value $f_i\in \{8,5\}$ of $W^{8,5}$.

We use the following lemmas on the sets of partial sums of Fibonacci words, which are easy consequences of part (3) of Proposition 6.

Lemma 7

Suppose that $b\leqslant a$. Then the set of partial sums of $w_a := W^{F_{a+1},F_a}$ is a subset of the set of partial sums of $W^{F_{b+1}, F_b}$. That is, let

$$\begin{aligned} PS(w_a)=\left\{ k:k=\sum _{i=0}^m W_i^{F_{a+1},F_a} \text { for some } m\right\} . \end{aligned}$$

Then $PS(w_a)\subseteq PS(w_b)$.

Proof

It suffices to check this when $b = a-1$. Then $\tau (y)=y$ gives $F_a\rightarrow F_{a}$ and $\tau (x) = yz$ gives $F_{a+1}\rightarrow F_{a}F_{a-1}$. This implies that each partial sum in the word $w_a$ is a partial sum in $w_b$. $\square$

In view of Lemma 7, it will be convenient to interpret the morphism as $\tau =\tau _\alpha$, where $x=F_{\alpha +1}$, $y=F_{\alpha }$ and $z=F_{\alpha -1}$, with transformation

• (1) $F_{\alpha +1}\rightarrow F_{\alpha }F_{\alpha -1}$

• (2) $F_\alpha \rightarrow F_\alpha$

for some $\alpha >1$. One application is the following.

Lemma 8

Suppose that $n\in PS(w_a)\setminus PS(w_{a+1})$. Then $n-F_{a+1}\in PS(w_{a+2})$.

Proof

Define m by $n=\sum _{i=0}^m W_i^{F_{a+1},F_a}$, and consider the alphabet $(y,z)=(F_{a+1},F_a)$, and the word $w_a=yzyyzyzy\ldots$ We note that $n\in PS(w_a)\setminus PS(w_{a+1})$ if and only if $f_m=y$ and $f_{m+1}=z$. This implies that $n-F_{a+1}\in PS(w_{a+1})$. Consider the morphism $\tau$ as defined in Proposition 6 (3). We replace each instance of yz in $w_a$ by $x=F_{a+2}$ (and leave the other y’s unchanged), thus obtaining the word $w_{a+1}=xyxxyxyxy\ldots$ We repeat the argument in going to $w_{a+2}$, and observe that the partial sum of all letters to the left of any x in $w_{a+1}$ will remain a partial sum in the word $w_{a+2}$. $\square$

Observe that $PS(w_1)={\mathbb {N}}$ (since $F_1=F_2=1$), so that every nonnegative integer is in some $PS(w_a)$. Furthermore, $\bigcap _{a\geqslant 1} PS(w_a)=\{0\}$, since the smallest nonzero element of $PS(w_a)$ is $F_{a+1}$.

Remark 9

We do not use this result in the paper, but it is possible to show that $PS(w_a)=\{n:z_1(n)\geqslant F_{a+1}\}$. This result would simplify some of the later proofs, but we prefer to highlight the connection with the hybrid and sturm positions in Sect. 6.

5 ${\mathcal {P}}$ positions in one-pile Fibonacci nim

The winning strategy for one-pile Fibonacci nim was described by Whinihan. Consider the position (n; r). If $z_1(n)\leqslant r$, then (n; r) is an ${\mathcal {N}}$ position, and removing $z_1(n)$ stones is a winning move. If $z_1(n)>r$, then (n; r) is a ${\mathcal {P}}$ position, and there are no winning moves.

It is also possible to characterize the ${\mathcal {N}}$ and ${\mathcal {P}}$ positions in terms of the Fibonacci word. This approach will be useful for our analysis of the multi-pile game.

Theorem 10

Fix a take-away size r. There is a unique Fibonacci number $F_t$ so that $F_t\leqslant r<F_{t+1}$. The position $(n;r)\in {\mathcal {P}}$ if and only if $n\in PS(w_{t})$ (n is a partial sum of $W^{F_{t+1},F_{t}}$), i.e. if and only if there is some m so that

$$\begin{aligned} n = \sum _{i=0}^m W^{F_{t+1},F_t}_i \end{aligned}$$

(1)

Proof

Suppose first that (n; r) is of the given form. We must demonstrate that there is no move to a position of the same form. Suppose that the new position is $(n-s;2s)$, with $s\leqslant r < F_{t+1}$, and let $b=b(s)$ be a function of s such that

$$\begin{aligned} F_b\leqslant 2s < F_{b+1}. \end{aligned}$$

(2)

Then $F_b\leqslant 2s< 2F_{t+1}<F_{t+3}$, gives $b\leqslant t+2$. With this notation, by splitting the problem into three cases, we prove that $n-s\not \in PS(w_{b})$.

Case $b\leqslant t$: since $s<F_b$, then (1) together with Lemma 7 gives the claim.

Case $b=t+1$: Given $n\in PS(w_{t})$ and (2), we prove that $n-s\not \in PS(w_{t+1})$. Suppose, for a contradiction, that $n-s\in PS(w_{t+1})$. Then, by $\tau (x)=yz$ and $\tau (y)=y$, interpreted as $\tau (F_{t+2})=F_{t+1}F_t$ and $\tau (F_{t+1})=F_{t+1}$, by $s<F_{t+1}$, we get $n\not \in PS(w_{t})$. Hence $n-s\not \in PS(w_{t+1})$.

Case $b=t+2$: Given $n\in PS(w_{t})$, by (2) $s<F_{t+2}$, we must prove that $n-s\not \in PS(w_{t+2})$. Observe that, by Lemma 8, if $n\in PS(w_{t})\setminus PS(w_{t+1})$, then $n-F_{t+1}\in PS(w_{t+2})$, which gives $n-s\not \in PS(w_{t+2})$, since $s<F_{t+2}$. Hence, we may assume that $n\in PS(w_{t+1})$, and so the argument is in analogy with case $b=t+1$.

Suppose next that (n; r) is not of the form in the statement of the theorem (and we must demonstrate that there is a move to a position of that form). Then there is a $\nu$ such that

$$\begin{aligned} \sum _{i=0}^\nu W^{F_{t+1},F_t}_i< n < \sum _{i=0}^{\nu +1} W^{F_{t+1},F_t}_i. \end{aligned}$$

(3)

There is a unique positive integer b so that $n\in PS(w_b)\setminus PS(w_{b+1})$. By Lemma 8, $n-F_{b+1}\in PS(w_{b+2})$. Since $F_{b+2}\leqslant 2F_{b+1}<F_{b+3}$, $(n-F_{b+1};2F_{b+1})$ is a ${\mathcal {P}}$-position. $\square$

6 Two-pile Fibonacci nim

6.1 The Zeckendorf approach

The ${\mathcal {P}}$ positions of the two-pile Fibonacci nim game $(m,m+k;r)$ can also be expressed in terms of the Zeckendorf representation as a generalization of that of the one-pile game. We think of it as if the smallest pile size m and the initial take-away amount r are fixed and the larger pile size varies.

Theorem 11

Let $m,k\geqslant 0$ and $r\geqslant 1$. Let t be such that $F_t\leqslant r<F_{t+1}$, and let e be such that $F_e=z_1(k)$. Then the following is a complete classification of the outcomes of the position $(m,m+k;r)$:

• (1) If $e\leqslant t$, then $(m,m+k;r)\in {\mathcal {N}}$.

• (2) If $e\geqslant t+2$, then $(m,m+k;r)\in {\mathcal {P}}$.

• (3) If $e=t+1$ and $m<F_t$, then $(m,m+k;r)\in {\mathcal {P}}$.

• (4) If $m\geqslant F_t$ and $e=t+1$, and either $z_2(k)=\infty$ or $z_2(k)=F_{t+d}$ where $m<F_t+F_{t+1}+\cdots +F_{t+d-3}$, then let s be the unique integer so that $F_t+F_{t+1}+\cdots +F_{t+s-1}\leqslant m<F_t+F_{t+1}+\cdots +F_{t+s}$. Then

  • (a) If s is odd, then $(m,m+k;r)\in {\mathcal {N}}$,

  • (b) If s is even, then $(m,m+k;r)\in {\mathcal {P}}$.

• (5) If $e=t+1$, and $z_2(k)=F_{t+d}$, and $m\geqslant F_t+F_{t+1}+\cdots +F_{t+d-3}$, then

  • (a) If d is odd, then $(m,m+k;r)\in {\mathcal {N}}$,

  • (b) If d is even, then $(m,m+k;r)\in {\mathcal {P}}$.

Remark 12

For $s\geqslant 1$, the partial sums $F_t+F_{t+1}+\cdots +F_{t+s-1}$ can be written more concisely:

$$\begin{aligned} F_t+F_{t+1}+\cdots +F_{t+s-1}= & {} (F_{t+2}-F_{t+1}) + (F_{t+3}-F_{t+2})\\ + \cdots + (F_{t+s+1}-F_{t+s})= & {} F_{t+s+1}-F_{t+1}. \end{aligned}$$

However, in this context it is more natural to leave the series unsummed, as it serves as a reminder of how the game might be played.

Since Theorem 11 is a bit complicated, let us say something about how it should be interpreted from a player’s point of view. First, if it is possible to remove $z_1(k)=:F_e$ stones from the $m+k$ pile, then either this move or removing $F_{e-1}$ stones from the m pile is winning. (See the proof for a more complete description of when to play each of these moves). If it is not possible to remove $z_1(k)$ stones from the $m+k$ pile, then every move in that pile is losing. However, there may still be winning moves in the m pile, and indeed the only move that might win is to remove $F_t$ stones from the m pile. If $z_1(k)\geqslant F_{t+2}$, then this move loses. If $z_1(k)=F_{t+1}$, then the situation is rather complicated, leading to cases (3)–(5) in the theorem. However, when actually playing the game, the structure of the theorem is not terribly important: if all moves except for one are clearly losing and the remaining one leads to complications, by all means play the complicated one!

We now turn to the proof. One key input is the following Lemma, which we used in our earlier work on the local move dynamic game:

Lemma 13

(Larsson and Rubinstein-Salzedo 2016, Lemma 4.3) Suppose $n>1$ and $1\leqslant k<z_1(n)$. Then $z_1(n-k)\leqslant 2k$.

Proof of Theorem 11

We work one case at a time. For the claimed ${\mathcal {N}}$ positions, we show that there is a move to a position that we claim to be in ${\mathcal {P}}$, and for the claimed ${\mathcal {P}}$ positions, we show that every move is to a claimed ${\mathcal {N}}$ position. By Proposition 3, the claimed ${\mathcal {N}}$ and ${\mathcal {P}}$ positions are, in fact, the ${\mathcal {N}}$ and ${\mathcal {P}}$ positions. Observe that every position of two-pile Fibonacci nim is of type (1), (2), (3), (4a), (4b), (5a), or (5b). Let us also note that if $k=0$, then the second player can mimic the first player, so such a position is always a ${\mathcal {P}}$ position. By our convention on $z_1$, such positions are always of type (2).

We begin with positions of type (1). Suppose first that $z_2(k)\geqslant F_{t+3}$. Then we can remove $z_1(k)=F_e$ stones from the $m+k$ pile to get to $(m,m+k-z_1(k);2z_1(k))$, which is of type (2), since $z_1(k-z_1(k))=z_2(k)\geqslant F_{t+3}$, which is at least as large as the second Fibonacci number after $2z_1(k)<F_{t+2}$. If $z_2(k)=F_{e+2}$ and $m<F_{e+1}$, then $(m,m+k-z_1(k);2z_1(k))$ is of type (3).

However, if $z_2(k)=F_{e+2}$ and $m\geqslant F_{e+1}$, then removing $z_1(k)$ stones yields a position of type (4) or (5). Instead, there is a winning move in the m pile, to $(m-F_{e-1},(m-F_{e-1})+(F_{e-1}+k);2F_{e-1})$; since $z_1(F_{e-1}+k)\geqslant F_{e+3}$, this position is of type (2).

Suppose we are in a position of type (2). Then we may move in the $m+k$ pile, to $(m,m+k-a;2a)$ for $1\leqslant a\leqslant r$, and since $r<z_1(k)$ and hence $a<z_1(k)$, Lemma 13 ensures that $z_1(k-a)\leqslant 2a$, so $(m,m+k-a;2a)$ is of type (1). We may also move in the m pile to $(m-a,(m-a)+(a+k);2a)$ for $1\leqslant a\leqslant \min (r,m)$, which is of type (1) since $z_1(a+k)=z_1(a)\leqslant a\leqslant 2a$.

Now, suppose we are in a position of type (3). Then the same arguments as for type (2) positions again shows that all moves from type (3) positions are to type (1) positions.

Now, suppose we are in a position of type (4) or (5). (We will distinguish the types more finely later). We may move in the $m+k$ pile to $(m,m+k-a;2a)$ for $1\leqslant a\leqslant r$, which is of type (1). We may also move in the m pile to $(m-a,(m-a)+(a+k);2a)$ for $1\leqslant a\leqslant \min (m,r)$. If $a\ne F_t$, then $z_1(a+k)=z_1(a)\leqslant a\leqslant 2a$, which is of type (1). The remaining move is to $(m-F_t,(m-F_t)+(F_t+k);2F_t)$, which is of type (4) or (5) if $m-F_t\geqslant F_{t+1}$ and $z_1(F_t+k)=F_{t+2}$, type (2) if $z_1(F_t+k)\geqslant F_{t+3}$, and type (3) if $m-F_t<F_{t+1}$ and $z_1(F_t+k) = F_{t+2}$. As a result, the only move from a position of type (4) or (5) that might be to a ${\mathcal {P}}$ position is the move to $(m-F_t,(m-F_t)+(F_t+k);2F_t)$, and only if this position is of type (4) or (5). When it is to another position of type (4) or (5), then it decreases s or d by one, depending on whether it is a type (4) or (5) position, respectively. Hence, a position $(m,m+k;r)$ of type (4) or (5) is a ${\mathcal {P}}$ position if the (unique) maximal sequence of moves to positions of type (4) or (5) has even length, and is an ${\mathcal {N}}$ position if the (unique) maximal sequence of moves to positions of type (4) or (5) has odd length. From a position of type (4), removing consecutive Fibonacci numbers from the m pile eventually results in a position of type (3), whereas from a position of type (5), removing consecutive Fibonacci numbers from the m pile eventually results in a position of type (2). Either way, this distinguishes types (4a) and (4b), as well as (5a) and (5b). $\square$

6.2 The word approach

As in the case of one-pile Fibonacci nim, it is possible to express the ${\mathcal {P}}$-positions of two-pile global Fibonacci nim in terms of partial sums of a word. We generalize Theorem 10; recall, a one pile position $(n;r)\in {\mathcal {P}}$ if and only if $n\in PS(w_{t})$, where $t=t(r)$ is such that $F_t\leqslant r<F_{t+1}$. For two piles, the ${\mathcal {P}}$ positions can also be described via an infinite word, but the construction is somewhat more technical. Some of the positions generalize directly the one pile case.

Definition 14

Fix the smallest pile size $m\geqslant 0$ in a position $(m,m+k;r)$, and define $p=p(m)\geqslant 0$ as a function of m such that $F_p\leqslant m < F_{p+1}$. If the take-away size $r < F_{p-1}$, then we say that the position $(m,m+k;r)$ is hybrid, and otherwise it is sturm.

Hence the sturm case applies for the one pile game, i.e. $m=0$, or if $p>1$ ($p=1$ does not apply) and $r\geqslant F_{p-1}$.

Definition 15

Fix the smallest pile size $m\geqslant 0$ in a position $(m,m+k;r)$, and let $p=p(m)$ be as in Definition 14. Then $\alpha =\alpha (r,p)$ is the function defined by $F_{p+\alpha -1}\leqslant r < F_{p+\alpha }$.

Note that a position is sturm if and only if $\alpha \geqslant 0$.

We will show that, for each choice of m and r, the numbers k for which the position $(m,m+k;r)$ is a ${\mathcal {P}}$-position can be described by the partial sums of an infinite word on two or three letters. When the word has only two letters (the sturm case) it is the Fibonacci word, where the Fibonacci letters depend on $\alpha$.

Definition 16

In case $\alpha \geqslant 0$ we consider the word $T^{\alpha }(w_p)$, where $p=p(m)$ is given by the smallest heap size as in Definition 14. If $\alpha = 0$, then the word is $T^0(w_p) = w_p = W^{F_{p+1},F_p}$. For $\alpha \in \{1,2\}$, the word is $T^1(w_p) = T^2(w_p) = W^{F_{p+2},F_{p+1}}$. For $\alpha \geqslant 3$, the word is $T^\alpha (w_p) = W^{F_{p+\alpha },F_{p+\alpha -1}}$.

For the hybrid games, we recursively build the relevant word for classifying the ${\mathcal {P}}$-positions. There are three possible transformations of a letter in a given word. In each word, each letter is one of three consecutive Fibonacci numbers. The words are given recursively, for a fixed m, by successively decreasing $\alpha$ (via a decrease in the take-away size r) and starting with the sturm case of $\alpha = 0$.

Given a word on the ordered alphabet $A=(x,y,z)$ (sometimes just (x, y)), where $x>y>z$, a possible transformation to the ordered alphabet $B = (y,z,v)$, with $y>z>v$, is the map $\tau$ given by

$\tau _1$ :

: $y\rightarrow y$ or $z\rightarrow z$

$\tau _2$ :

: $x\rightarrow yz$ or $y\rightarrow zv$

$\tau _3$ :

: $x\rightarrow zvz$,

We write “possible transformations” because more information is needed to say when $\tau =\tau _i$. (Note the similarity of $\tau _3$ with the second iteration of the Fibonacci morphism, that is, the word $S_2$ in Proposition 6).¹ For example, starting with the Fibonacci word on the alphabet $A=(x,y)$, we produce a ‘generalized Fibonacci word’ on the alphabet $B=(y,z,v)$, by applying $\tau _3$ and $\tau _1$:

$$\begin{aligned} xyxxyxyx\cdots \mapsto zvzyzvzzvzyzvzyzvz\cdots . \end{aligned}$$

In applications, we let these transformations be

$\tau _1$ :

: $F_i\mapsto F_{i}$

$\tau _2$ :

: $F_i\mapsto F_{i-1}F_{i-2}$

$\tau _3$ :

: $F_i\mapsto F_{i-2}F_{i-3}F_{i-2}$,

for some i, related to $\alpha$; we will use these three transformations to construct a morphism $\xi :A^*\rightarrow B^*$, and a sequence of infinite words $\{T^{\alpha , m}(w_p)\}_{\alpha \leqslant 0}$, with $T^{0, m}(w_p)=w_p$. Here $A^*$ and $B^*$ denote the sets of all words with letters in the alphabets A and B, respectively.

Definition 17

Consider the hybrid position $(m,m+k;r)$, with $F_p\leqslant m<F_{p+1}$, and define $\alpha =\alpha (p,r)\leqslant 0$ by $F_{p+\alpha -1}\leqslant r < F_{p+\alpha }$. Let $\eta =\eta (m,p) = F_{p+1} - m$. Let $T^{0,m}(w_p)=w_p$. The composite transformation

$$\begin{aligned} \xi =\xi ^{\alpha ,m}:T^{\alpha ,m}(w_p)\mapsto T^{\alpha -1,m}(w_p) \end{aligned}$$

is special if $F_{p+\alpha -1} < \eta \leqslant F_{p+\alpha }$, and otherwise it is standard. If $\xi$ is standard then we apply $\tau _3$ to the largest Fibonacci letter in $T^{\alpha ,m}(w_p)$, and $\tau _1$ to the other letter(s).

In case $\xi$ is special, the translation of a letter depends also on the Fibonacci word $w_p$; in particular the translation depends on whether $\alpha$ is even (Example 20) or odd (Example 21). Consider a word W. Denote the partial sum of all letters with index less than i by W(i). Consider the ith letter $f_i$ in $T^{\alpha ,m}(w_p)$. In case $\alpha$ is

even :

if $f_i=x$ is the largest letter, then $\tau (x)=\tau _2(x)=yz$ if $T^{\alpha ,m}(w_p)(i)\in PS(w_p)$, and otherwise $\tau (x)=\tau _3(x)=zvz$. If $f_i$ is not the largest letter, then $\tau (f_i)=\tau _1(f_i)=f_i$.

odd :

if $f_i=y$ is the second largest letter, then $\tau (y)=\tau _2(y)=zv$ if $T^{\alpha ,m}(w_p)(i)\in PS(w_p)$, and otherwise $\tau (y)=\tau _1(y)=y$. If $f_i=x$ is the largest letter, then $\tau (x)=\tau _3(x)=zvz$, and, if $f_i=z$ is the smallest letter, $\tau (z)=\tau _1(z)=z$.

By this definition it follows that the smallest letter is about the size of the take away size, for all $\alpha$.

Lemma 18

The smallest letter in $T^{\alpha ,m}(w_p)$ is $F_{p + \alpha - 1}$, except for the sturm case, if $0\leqslant \alpha \leqslant 1$, then the smallest letter is $F_{p + \alpha }$. The largest letter is two indexes larger than the smallest in the hybrid case and one index larger than the smallest in the sturm case.

Proof

The standard case is by definition. In the hybrid case, note that, for each iteration, the largest letter uses $\tau _3$ and $\tau _2$, in either combination they give the claim. $\square$

Let us give three generic examples of how the hybrid case applies, beginning with the standard transformation.

Example 19

Suppose that the smallest heap size is $m=26$. Then $F_p=21$. If $r=13\geqslant F_{p-1}$ then $\alpha =0$ and we obtain a Sturmian word, namely $w_{8}$. Now, if the take-away size r decreases from 13 to 12 (with the other parameters fixed), then $\alpha$ changes from 0 to $-1$, and so $\xi : T^{0,26}(w_8)\mapsto T^{-1,26}(w_8)$ is

$$\begin{aligned}&[34, 21, 34, 34, 21, 34, 21, 34, \ldots ]\\&\quad \mapsto [13, 8, 13, 21, 13, 8, 13, 13, 8, 13, 21, 13, 8, 13, 21, 13, 8, 13,\ldots ]. \end{aligned}$$

This means that we start with the Fibonacci word on the alphabet $A=(x,y)=(34,21)$ and then apply $\tau _1$ to $y=21$ and $\tau _3$ to $x=34$, obtaining an infinite word on the alphabet $B=(y,z,v)=(21,13,8)$.

As we saw in Definition 17, there are only three types of composite transformation in the hybrid case (although there are infinitely many $T^{\alpha ,m}$). A change in $\alpha$ gives a new word (without exception), and to know the precise change, the smallest heap size m has to be taken into account. The case $\tau _2$ occurs only in special cases, concerning the two largest letters (the smallest letter uses only $\tau _1$).

Example 20

(Special, even) Here we let $m=26$, so that again $p=8$, but now with the take-away sizes $r: 5\mapsto 4$, so that $\alpha :-2\mapsto -3$, and so $\xi : T^{-2,26}(w_8)\mapsto T^{-3,26}(w_8)$ is

$$\begin{aligned}&[13, 8, 13, 8, 5, 8, 13, 8, 13, 13, 8, \ldots ]\\&\quad \mapsto [8, 5, 8, 5, 3, 5, 8, 5, 8, 8, 5, 8, 5, 3, 5, 8, 5, 8, \ldots ]. \end{aligned}$$

In this example, the largest letter “13” becomes “8, 5”, (i.e. $\tau _2$) if the partial sum of all lower terms belongs to $PS(w_{9})$, and otherwise “13” becomes “5, 3, 5” (i.e. $\tau _3$). The second largest letter “8” does not change (i.e. $\tau _1$).

This means that we start with the Fibonacci word on the alphabet $A=(x,y,z)=(13,8,5)$ and apply $\tau _1$ to $y=8$ and $\tau _3$ to $x=13$, obtaining an infinite word on the alphabet $B=(y,z,v)=(8,5,3)$. This is a special transformation, because $\eta =F_{p+1}-m=34-26=8=F_6=F_{p-2}$.

Example 21

(Special, odd) Let $m=25$ (so that $p=8$) and let $r: 8\mapsto 7$, so that $\alpha :-1\mapsto -2$. The map $\xi : T^{-1,25}(w_8)\mapsto T^{-2,25}(w_8)$ is

$$\begin{aligned}&[13, 8, 13, 21, 13, 8, 13, 13, 8, 13\ldots ]\\&\rightarrow [8, 5, 8, 13, 8, 5, 8, 8, 5, 8, 13, 8, 5, 8, 13\ldots ]. \end{aligned}$$

In this example, “13” changes to “8, 5” ($\tau _2$) if the partial sum of all lower terms belongs to $PS(w_{9})$ (or $PS(w_{8})$), and otherwise it does not decompose ($\tau _1$). In either case, “21” decomposes to $``8,5,8''$ ($\tau _3$) and “8” does not decompose ($\tau _1$). For reference to the special transformation, here $\eta =34-25=9\leqslant F_7=F_{p-1}$.

Of course, in general, for each $F_p\leqslant m<F_{p+1}$, there are $\alpha$ not defined by any r. We get that $\alpha \geqslant -p+3$, for otherwise, by $F_{p+\alpha -1}\leqslant r < F_{p+\alpha }$, $r < F_2$, which is impossible. In the hybrid case this implies $3<p$, so $3 = F_4\leqslant m$. Let us give an example of how the recursive application of $\tau$ terminates in case of the special transformation.

Example 22

As evidenced, in the hybrid case $m\geqslant 3$, but, in case of a special transformation, we get $m\geqslant 4$ ($m=3$ gives $p=4$ and $\eta = 2$, which gives $\alpha = 0$ by $F_{3+\alpha } < \eta = 2 \leqslant F_{4+\alpha }$). On the other hand $m=4$ gives $r=1$, so let us instead study the first play game case, $r=2$ and $m=5$. By $p=5$, then $\alpha = -1$. Obviously, $T^{0,5}(w_5)=w_5=[8,5,8,8,5,8,\ldots ]$, and the first transformation is standard, giving the new alphabet (5, 3, 2), and the word $T^{-1,5}(w_5)=[3, 2, 3, 5, 3, 2, 3, 3, 2, 3, 5, 3, 2, 3, 5, 3, 2, 3\ldots ]$. Next, because $\alpha =-1$ is odd,

$$\begin{aligned} \xi (T^{-1,5}(w_5))=T^{-2,5}(w_5)=[2,1, 2, 3, 2,1,2, 2,1, 2, 3, 2,1, 2, \ldots ]. \end{aligned}$$

(4)

Consider $m=5$ with $\alpha =-3$. By definition this means that $F_1\leqslant r < F_2$, which is impossible, hence, for $m=5$, $\tau$ terminates with the word (4).

We state the main result of this section.

Theorem 23

The position $(m,m+k;r)\in {\mathcal {P}}$, with $F_p\leqslant m<F_{p+1}$, if and only if, in the sturm case, $k\in PS(w_{p+\alpha })$ if $0\leqslant \alpha \leqslant 1$ and $k\in PS(w_{p+\alpha -1})$ if $\alpha > 1$, and otherwise, in the hybrid case, $k\in PS(T^{\alpha ,m}(w_p))$.

The proof is similar to that of Theorem 10. There are more tedious details to check, but all the ideas and techniques are similar.

7 Multi-pile Fibonacci nim

The following theorem about (ordinary) nim is well-known:

Theorem 24

(Bouton) If $(n_1,\ldots ,n_k)$ is a nim position, then there is a unique nonnegative integer b for which $(n_1,\ldots ,n_k,b)\in {\mathcal {P}}$. Furthermore, $b<2\max (n_1,\ldots ,n_k)$ and $b\leqslant n_1+\cdots +n_k$.

Remark 25

This follows easily from Bouton’s description of the winning strategy in nim, but it is also possible to prove it (say, by induction on the largest power of 2 occurring in any $n_i$) without using the winning strategy.

It would be desirable to have a similar statement for multi-pile Fibonacci nim. However, the best we can do is the following:

Theorem 26

If $(n_1,\ldots ,n_k;\infty )$ is a multi-pile Fibonacci nim position, then there is at most one nonnegative integer b for which $(n_1,\ldots ,n_k,b;\infty )\in {\mathcal {P}}$. When it exists, we call b the complementary value of $(n_1,\ldots ,n_k)$.

Proof

Suppose that $(n_1,\ldots ,n_k,b;\infty )\in {\mathcal {P}}$, and suppose that $b'>b$. Then there is a move from $(n_1,\ldots ,n_k,b';\infty )$ to $(n_1,\ldots ,n_k,b;b'-b)$. But the latter is a ${\mathcal {P}}$ position, since its options are a subset of those of $(n_1,\ldots ,n_k,b;\infty )$, which is itself a ${\mathcal {P}}$ position. Hence $(n_1,\ldots ,n_k,b';\infty )\in {\mathcal {N}}$. $\square$

Remark 27

It remains an open question to determine a bound on the complementary value, when it exists. It appears that most of the time, the complementary value is “not too much larger” than the maximum of the $n_i$’s. However, there are some notable exceptions; for instance:

• $(1,47,72;\infty )\in {\mathcal {P}}$,

• $(2,41,139;\infty )\in {\mathcal {P}}$,

• $(2,93,345;\infty )\in {\mathcal {P}}$,

• $(8,9,53;\infty )\in {\mathcal {P}}$.

See Table 1 for a table of values of complementary values.

Table 1 Complementary values of Fibonacci nim

A curious aspect of Theorem 26 is the possibility that there may not be a complementary value for a Fibonacci nim position. It turns out that Fibonacci nim positions with no complementary values do exist.²

Theorem 28

For any nonnegative integer n, $(3,4,n;\infty )\in {\mathcal {N}}$.

Proof

The following four classes partition the nonnegative integers.

• (1) $B-2=PS(w_3)=\{n:z_1(n)\geqslant 3\}=\{0,3,5,8,11,13,16,18,21,\ldots \}$,

• (2) $AB-2=1+PS(w_4)=\{n:z_1(n-1)\geqslant 5\}=\{1,6,9,14,19,22,27,\ldots \}$,

• (3) $AB-1=2+PS(w_4)=\{n:z_1(n-2)\geqslant 5\}=\{2,7,10,15,20,23,28,\ldots \}$,

• (4) $BB-1=4+PS(w_5)=\{n:z_1(n-4)\geqslant 8\}=\{4,12,17,25,33,38,\ldots \}$.

(Recall that $F_3=2$, so that $PS(w_3)$ consists of partial sums with letters 3 and 2, and so forth).

Remark 29

The names for these sets come from the theory of complementary equations. We let $a(n)=\lfloor \phi n\rfloor$ and $b(n)=\lfloor \phi ^2 n\rfloor$, where $\phi =\frac{1+\sqrt{5}}{2}$. Then A consists of all numbers of the form a(n) for some $n\geqslant 1$, B consists of all numbers of the form b(n) for some n, AB consists of all numbers of the form a(b(n)) for some n, and so forth. See Clark (2008) for more details on complementary equations.

Adding one to each set gives the sets, $B-1 = AA$, $AB-1 = BA$, AB and BB. The sets AA and AB partition A and the sets BA and BB partition B. A and B partition the positive integers.

We claim that the following moves are to ${\mathcal {P}}$ positions:

• (1) If $n\in B-2$, then $(3,3,n;2)\in {\mathcal {P}}$.

• (2) If $n\in AB-2$, then $(2,4,n;2)\in {\mathcal {P}}$.

• (3) If $n\in AB-1$, then $(1,4,n;4)\in {\mathcal {P}}$.

• (4) If $n\in BB-1$, then $(0,4,n;6)\in {\mathcal {P}}$.

Part (4) of the claim follows from Theorem 23, since it is the 2-pile Sturm game $(4,4+k;6)$ on the word $w_5$. Let us list the moves for the respective three first types (enumerating as above, and with n belonging to respective subclass):

• (1) $(3,3,n-x;2x), 1\leqslant x\leqslant 2$, (2, 3, n; 2), (1, 3, n; 4) (we may assume $n>0$).

• (2) $(2,4,n-x;2x), 1\leqslant x\leqslant 2$, (2, 3, n; 2), (2, 2, n; 4), (1, 4, n; 2), (0, 4, n; 4).

• (3) $(1,4,n-x;2x), 1\leqslant x\leqslant 4$, (0, 4, n; 2), (1, 3, n; 2), (1, 2, n; 4), (1, 1, n; 6), (0, 1, n; 8).

We must show that all of these positions are in ${\mathcal {N}}$. To do this, we show that all of the following positions are in ${\mathcal {P}}$:

• (i) $(0,1,n;2)\in {\mathcal {P}}$ if $n\in B-1$, and $(0,1,n;6)\in {\mathcal {P}}$ if $n\in BB-3\subset AB-2\subset B-1$.

• (ii) $(0,2,n;4)\in {\mathcal {P}}$ if $n\in AB-1$.

• (iii) $(0,3,n;2)\in {\mathcal {P}}$ if $n\in AB=\{3,8,11,16,21, 24\ldots \}\subset B-2$.

• (iv) $(1,1,n;2)\in {\mathcal {P}}$ if $n\in B-2$ and $(1,1,n;4)\in {\mathcal {P}}$ if $n\in BB\subset B-2$.

• (v) $(1,2,n; 2)\in {\mathcal {P}}$ if $n\in BB-1$.

• (vi) $(1,3,n; 2)\in {\mathcal {P}}$ if $n\in AB-2$.

• (vii) $(2,2,n;2)\in {\mathcal {P}}$ if $n\in B-2$ and $(2,2,n;4)\in {\mathcal {P}}$ if $n\in BB\subset B-2$.

• (viii) $(2,3,n;2)\in {\mathcal {P}}$ if $n\in AB-1$.

We begin by observing that in some cases a move from a candidate ${\mathcal {P}}$ position in some class can be reversed (by the other player), to another ${\mathcal {P}}$ position (by induction) in the same class. This happens whenever the current letter in the relevant word (for this class) is sufficiently small and the current player’s move is sufficiently large (on the third pile). Let us explain this terminology. Say that the alphabet describing the P-positions is (3, 2), as in (1) above, and that the word used for the third pile size is $w_3$. Denote the ith letter in $w_3$ by $f_i$, and we consider $\sum _{i\leqslant j} f_i$, representing the size of the third pile, for some j. By induction, each ${\mathcal {P}}$ position corresponds to some $\sum _{i\leqslant j'} f_i$, $j'<j$ (the base case is $(3,3,0;\cdot )\in {\mathcal {P}}$). A removal of x on this pile corresponds to $\sum _{i\leqslant j} f_i \, - x$. If $x=1$, it is not possible to reverse the position to a position in the same class. In fact the only problematic case is if the current letter $f_j = 3$ and $x=1$. But this case is resolved by instead using (viii) above; $(2,3,n;2)\in {\mathcal {P}}$ if $n\in AB-1$, namely $\sum _{i\leqslant j} f_i \, -1\in AB-1$, since the current letter is 3 (see Clark (2008) for further details on solutions to such equations). If $f_j=2$, then there is the case that the current player removes $x=2$ from the third pile. But then, by induction, the move is to an ${\mathcal {N}}$-position, since the new take-away size is 4.

By the observation in the previous paragraph, we are done with the first case in (1). Moreover, from (2, 3, n; 2) we can move to the candidate ${\mathcal {P}}$ position (2, 2, n; 2) (vii), and from (1, 3, n; 4) we can move either to (1, 1, n; 4), if $n\in BB=(B-2)\setminus AB$, or to (0, 3, n; 2), if $n\in AB\subset (B-2)$.

Next, we verify that each candidate ${\mathcal {N}}$ position in (2) above has a move to a candidate ${\mathcal {P}}$ position. Here $0 < n\in AB-2$ and the alphabet is (5, 3). For positions of the form $(2,4,n-x;2x)$, $2x\leqslant 4$, in case the current letter is $f_j$, then if $f_j-x=1$, the position can be reversed to a candidate ${\mathcal {P}}$ position of the same type. One of the exceptional cases is when the current letter is $f_j=5$ and $x=1$. In this case, $n-1\in BB$, so that $(2,2,n-1;4)$ is a ${\mathcal {P}}$ position by (vii). (In fact, we have that $BB\subset AB-3\subset B-2$). There are more variations to verify for the first case, but they are all similar. For the remaining three proper three-pile cases, we have just seen that $(2,2,n-1;4)$ is a ${\mathcal {P}}$ candidate; it remains to note that both (2, 3, n; 2) and (1, 4, n; 2) have options to the candidate ${\mathcal {P}}$ position (1, 3, n; 2).

For case (3), we consider $n\in AB-1$, so it is similar to (2): one of the cases where a move does not have a reversible option is when $x=1$ and the current letter is 5. In any case, the option $(1,3,n-1;2)$ is a candidate ${\mathcal {P}}$ position, and this also suffices for (1, 3, n; 4). There are two more proper 3-pile candidate ${\mathcal {N}}$ positions of this form: (1, 2, n; 4) reverses to $(0,2,n-1;2)$ which is a ${\mathcal {P}}$ candidate, and from (1, 1, n; 6), there is an option $(1,1,z;2(n-z))$, with $z \in B-2$, because the maximum take-away size is 6. Hence, we have demonstrated how to find ${\mathcal {P}}$ positions (by induction) for all the ${\mathcal {N}}$ candidates of the forms in (1)–(3).

Next, we show that for each ${\mathcal {P}}$ candidate in (i) to (viii), there is no ${\mathcal {P}}$-position as an option. Let us begin to show that (1, 1, z; 2) is reversible. The two-stone removal is reversible, by the above argument, and the move to $(1,1,z-1;2)$ reverses to a position of the same form, unless the current letter is a 3. In this case there is a response to $(0,1,z-2;2)$, and where $z-2\in AB-2$, which is a ${\mathcal {P}}$ position, by Theorem 23. This response is also possible from (0, 1, z; 2), which concludes this case.

For a candidate ${\mathcal {P}}$ position of the form (1, 2, z; 2), note that $BB-3\subset AB-1$, and so both (0, 2, z; 2) and $(1,2,z-2;4)$ reverse to the ${\mathcal {P}}$ position $(0,2,z-2;r)$, $r=2,4$ respectively. A move to (1, 1, z; 2) reverses to the ${\mathcal {P}}$ position $(1,1,z-1;2)$, because $z-1\in B-2$. A move to (0, 1, z; 4) reverses to $(0,1,z-3;6)$, which is a ${\mathcal {P}}$ position (by Theorem 23). The move to $(1,2,z-1;2)$, reverses to $(1,1,z-1;2)$, which is a ${\mathcal {P}}$ position because $z-1\in B-2$.

For the position (1, 3, z; 2), with $z\in AB-2$, if two stones are removed from the third pile, the position reverses to one of the same form. Similarly, from $(1,3,z-1; 2)$, it suffices to study the “5” letter case, and thus $z-1\in BB$; there is a response to $(1,1,z-1; 4)\in {\mathcal {P}}$. Next, consider (1, 2, z; 2), with $z\in AB-2$; then respond to $(0,1,z; 4)\in {\mathcal {P}}$. Consider (1, 1, z; 4), with $z\in AB-2$; then respond to $(0,1,z; 2)\in {\mathcal {P}}$. The options (0, 1, z; 6) and (0, 3, z; 2), with $z\in AB-2$, are both ${\mathcal {N}}$ positions, by Theorem 23.

For the position (2, 2, z; r), with $z\in B-2$ and $r=2,4$, playing on the third pile is reversible to a position of the same type. Playing on the first pile, (1, 2, z; 2) reverses to (1, 1, z; 2) and playing to (0, 2, z; 4), gives an ${\mathcal {N}}$ position, by Theorem 23.

For the position (2, 3, z; 2), with $z\in AB-1$, playing on the third pile, it suffices to find a winning response to the option $(2,3,z-1; 2)$ when the current letter is a “5,” and therefore with $z-1\in BB-3\subset AB-2$. The option $(1,3,z-1; 2)\in {\mathcal {P}}$ suffices (so the letter “5” is not important). The same response obviously works for the option (1, 3, z; 2). The remaining options to check are (0, 3, z; 4) (which is an ${\mathcal {N}}$ position by Theorem 23), (2, 2, z; 2), and (1, 2, z; 4). These options have responses to $(0,2,z; r)\in {\mathcal {P}}$, for $r=2,4$. $\square$

Question 30

Are there any other two-pile Fibonacci nim positions $(n_1,n_2;\infty )$ (besides $(3,4;\infty )$) with no complementary value?

8 An easier variant: global power-of-two nim

power-of-two nim is a simpler variant of Fibonacci nim. In the classical (one-pile) formulation, the rules are the same as in Fibonacci nim, except that if the previous player removed m stones, then the next player may only remove at most m stones. Thus, the move dynamic can only stay the same or decrease on each move.

The winning strategy is closely related to that of Fibonacci nim, but it relies on the binary representation of n rather than the Zeckendorf representation. A winning strategy is to remove the smallest bit from the binary representation of the pile size on each move, and a position is a ${\mathcal {P}}$ position if and only if the smallest bit is larger than the move dynamic.

We represent the multi-pile global power-of-two nim game using the same notation as we do the multi-pile global Fibonacci nim game. It turns out that we can describe the ${\mathcal {P}}$ positions of multi-pile power-of-two nim completely. Let $a\oplus b$ denote the nim sum of a and b, and let $\mathfrak {sb}(n)$ denote the smallest power of 2 in the binary expansion of n, i.e. if $n=2^{a_1}+\cdots +2^{a_k}$ where the $a_i$’s are distinct powers of 2 with $a_1<\cdots <a_k$, then $\mathfrak {sb}(n)=2^{a_1}$. (If $n=0$, then we define $\mathfrak {sb}(n)=\infty$). Then we have the following:

Theorem 31

The power-of-two nim game $(n_1,\ldots ,n_k;r)\in {\mathcal {P}}$ if and only if $\mathfrak {sb}(n_1\oplus \cdots \oplus n_k)>r$.

Corollary 32

The power-of-two nim game $(n_1,\ldots ,n_k;\infty )\in {\mathcal {P}}$ if and only if the nim game $(n_1,\ldots ,n_k)\in {\mathcal {P}}$.

Proof of Theorem 31

The idea is to mimic good play in nim, playing a move that makes partial progress toward a winning nim move. To this end, we show that, given a position that we claim to be an ${\mathcal {N}}$ position, there is a move to a position that we claim to be a ${\mathcal {P}}$ position, whereas given a claimed ${\mathcal {P}}$ position, all moves are to claimed ${\mathcal {N}}$ positions. By Proposition 3, this shows that the ${\mathcal {P}}$ positions are exactly as we claim them to be.

First, suppose that $(n_1,\ldots ,n_k;r)$ is a power-of-two nim position with $\mathfrak {sb}(n_1\oplus \cdots \oplus n_k)\leqslant r$. Then there is some move $n_i\rightarrow n_i'$ that is a winning move in nim. Let $2^a=\mathfrak {sb}(n_1\oplus \cdots \oplus n_k)$. Then $2^a\leqslant r$, so removing $2^a$ stones from pile i is a legal move, to $(n_1,\ldots ,n_i',\ldots ,n_k;2^a)$. But now $\mathfrak {sb}(n_1\oplus \cdots \oplus n_i'\oplus \cdots \oplus n_k)\geqslant 2^{a+1}$, so this position is a claimed ${\mathcal {P}}$ position.

On the other hand, suppose that $\mathfrak {sb}(n_1\oplus \cdots \oplus n_k)>r$, and consider the move $n_i\rightarrow n_i'$, where $n_i-n_i'\leqslant r$. Then $\mathfrak {sb}(n_1\oplus \cdots n_i'\oplus \cdots \oplus n_i)=\mathfrak {sb}(n_i-n_i')$, so the position $(n_1,\ldots ,n_i',\ldots ,n_k;n_i-n_i')$ is a claimed ${\mathcal {N}}$ position. This completes the proof of Theorem 31. $\square$