An Aperiodic Subtraction Game of Nim-Dimension Two

Urban Larsson^{1} Department of Mathematics and Statistics Dalhousie University 6316 Coburg Road P.O. Box 15000 Halifax, NS B3H 4R2 Canada

                  urban031@gmail.com

Nathan Fox Department of Mathematics Rutgers University 110 Frelinghuysen Road Piscataway, NJ 08854 USA

                 fox@math.rutgers.edu

Abstract

In a recent manuscript, Fox studied infinite subtraction games with a finite (ternary) and aperiodic Sprague-Grundy function. Here we provide an elementary example of a game with the given properties, namely the game given by the subtraction set {F_{2n+1}− 1}, where F_{i} is the ith Fibonacci number, and n ranges over the positive integers.

1Supported by the Killam Trust.

1 Introduction

In a recent preprint, Fox [2] studied infinite and aperiodic subtraction games [1, p. 84] with a finite, ternary, Sprague-Grundy function. For an impartial game, the Sprague-Grundy value is computed recursively as the least nonnegative integer not in the set of values of the move options, and starting with the terminal position(s) which have Sprague-Grundy value zero [9, 3]. In this note we provide an elementary example of a game with the given properties. In particular, this means our game has nim-dimension two^{2}.

Let ϕ = \frac{1+\sqrt{5}}{2} denote the golden ratio. Let A(n) = ⌊nϕ⌋, B(n) = ⌊nϕ^{2}⌋, and AB(n) = A(B(n)) = A(n) + B(n) = 2⌊nϕ⌋ + n for all nonnegative integers n; see also Kimberling’s paper [4]. Then, define sets A = {A(n)}_{n⩾1}, B = {B(n)}_{n⩾1}, and AB = {AB(n)}_{n⩾1}. Further, let B_{0} ⊕ 1 = {B(n) + 1}_{n⩾0}, and AB ⊕ 1 = {2⌊nϕ⌋ + n + 1}_{n⩾1}. (In general, we let X_{0} = X ∪ {0} if X is a set of integers.) It is worth noting that if the sets defined here are thought of as sequences, they all appear in the OEIS [10]. A appears as \underline{A000201}, B as \underline{A001950}, AB as \underline{A003623}, B_{0} ⊕ 1 as \underline{A026352}, and AB ⊕ 1 as \underline{A089910}.

Throughout this paper, we will use F_{i} to denote the ith Fibonacci number (F_{1} = F_{2} = 1 and so on). We will frequently use the following famous numeration system: each positive integer is expressed uniquely as a sum of distinct non-consecutive Fibonacci numbers of index at least two. Though this representation has been discovered independently many times [5, 7, 13], it is typically referred to as the Zeckendorf representation. It is well known that x ∈ A if and only if the smallest Fibonacci term in the Zeckendorf representation of x has an even index [9]. Let z_{i} = z_{i}(x) denote the ith smallest index of a Fibonacci term in the Zeckendorf representation of the number x. Then, the set A contains all the numbers with z_{1} ⩾ 2 even. Further, for all n, B(n) is the left-shift of A(n); that is, the set B contains all the numbers with z_{1} ⩾ 3 odd. Another well-known Fibonacci-type representation of integers is the least-odd representation (which Silber [9] calls the second canonical representation), where the smallest index is odd ⩾ 1 and no two consecutive Fibonacci numbers are used. Let ℓ_{i}(x) denote the ith smallest index in the least-odd representation of x. Then ℓ_{1} is odd. By using this representation we find that A(n) is the left-shift of n for any positive integer n. That is, if n = F_{ℓ_{j}} + ⋯ + F_{ℓ_{1}}, then A(n) = F_{ℓ_{j}+1} + ⋯ + F_{ℓ_{1}+1}.

2 Our construction

In this section, we will construct our example of an aperiodic subtraction game. Let S = {F_{2n+1} − 1} = {1, 4, 12, …}, where n ranges over the positive integers. The two-player subtraction game S is played as follows. The players alternate in moving. From a given position, a nonnegative integer, p, the current player moves to a new integer of the form p − s ⩾ 0, where s ∈ S. A player unable to move, because no number in S satisfies the inequality, loses. Our main result states that the sequence of Sprague-Grundy values for this game is a ternary, aperiodic sequence. First, we need the following lemma.

2The number of power-of-two-components defines the group of nim-values generated by the games; this group is of order four so the dimension is two. In the classical definition [8], this dimension would have been one.

Lemma 1. The sets B_{0}, B_{0} ⊕ 1, AB ⊕ 1 partition the nonnegative integers.

Proof. By the work of Wythoff [12], it suffices to prove that the sets B ⊕ 1 and AB ⊕ 1 partition the set A.

Claim: For numbers in AB ⊕1, we get z_{2} ⩾ 4 even and z_{1} = 2. (Hence AB ⊕1 ⊂ A.) The claim is proved by noting that the least-odd representation coincides with the Zeckendorf representation for numbers of the form B(n). Hence AB(n) is the left-shift of B(n), which proves the claim, since z_{1}(B(n)) ⩾ 3.

We must also show that B_{0} ⊕ 1 ⊂ A contains all representatives with z_{1} ⩾ 4 even. This follows, since B contains all representatives with z_{1} = 3 odd (since F_{4} = F_{3} + 1, F_{6} = F_{5} + F_{3} + 1 and so on). Further, since B contains all representatives with z_{1} ⩾ 5 odd, B ⊕ 1 contains all representatives with z_{2} ⩾ 5 odd and z_{1} = 2. Finally, this set also contains the representative with just z_{1} = 2.

Note that because the golden ratio is an irrational number, the sets in Lemma 1 are aperiodic when thought of as sequences (in fact they follow a beautiful fractal pattern [6, Thm. 2.1.13, p. 51] related to the Fibonacci morphism).

We can now prove our main theorem.

Theorem 2. The Sprague-Grundy value of the subtraction game S is g(p) = 0 if p ∈ B_{0}, g(p) = 1 if p ∈ B_{0} ⊕ 1 and g(p) = 2 if p ∈ AB ⊕ 1.

Proof. We begin by showing that, if p ∈ B_{0}, then no follower of p is in B_{0}, which corresponds to showing that g(p) = 0. This holds for p = 0. Thus, it suffices to show that x = x(i) = p−F_{2i+1} +1 ∈ A, for all i > 0 such that p ⩾ F_{2i+1}, which is true if and only if the Zeckendorf representation’s smallest term is even indexed, i.e. z_{1}(x) is even. It holds trivially unless p−F_{2i+1} has as the smallest term F_{3} or F_{2}. In case the former, then we compute F_{3} +F_{2} and get F_{4}. Unless F_{5} is contained in the representation we are done. Continuing this argument gives the claim in the first case.

We show next that z_{1}(p − F_{2i+1}) > 2. Observe that

z_{1}(p) ⩾ 3 is odd.  (1)

If z_{1}(p) > 2i + 1, that is, if the smallest Zeckendorf term, say F_{2j+1}, in p has index greater than 2i + 1, then

F_{2j+1} − F_{2i+1} = F_{2j} + ⋯ + F_{2i+2}.  (2)

Hence, in this case, z_{1}(x) ⩾ 3, so F_{2} is not the smallest term. The case i = j is trivial. Hence j < i, i.e. z_{1}(p) < 2i + 1, which implies z_{1}(p − F_{2i+1}) ⩾ 2j + 1 > 2, by (1).

Suppose next that p ∈ B_{0} ⊕ 1. We need to show that there is a follower in B_{0}, but no follower in B_{0} ⊕ 1. Let b = p − 1 ∈ B_{0}. Then b + 1 − (F_{2i+1} − 1) = b − F_{2i+1} + F_{3} ∈ B if i = 1 (which solves the first part). Suppose now, that p has a follower in B_{0} ⊕ 1. Then b + 1 − (F_{2i+1} − 1) ∈ B_{0} ⊕ 1, that is b − (F_{2i+1} − 1) ∈ B_{0}, which is contradictory by the first paragraph.

At last we prove that if p ∈ AB ⊕ 1 then p has both a follower in B_{0} and in B_{0} ⊕ 1, but no follower in AB ⊕ 1. We begin with the latter. Note that z_{1}(p) = 2.

We want to show that p − F_{2i+1} + 1 ∉ AB ⊕ 1, for all i. Thus, it suffices to show α = p − F_{2i+1} ∉ AB. We may assume that there is a smallest k such that F_{k} ⩾ F_{2i+1}, and where F_{k} is a term in the Zeckendorf representation of p. Claim: If k is odd, then α ∈ A\AB, and otherwise α ∈ B ∪ (A \ AB). It suffices to prove this claim to prove this case. For the first part it is easy to see that z_{1}(α) = 2, since z_{1}(p) = 2 and by (2). If k is even, then we study the greatest Zeckendorf term in p, smaller than F_{2i+1}, say F_{ℓ} with existence of ℓ ⩽ 2i clear by definition of p. If ℓ = 2i, then F_{k} + F_{ℓ} − F_{2i+1} = y + 2F_{2i} = y + F_{2i+1} + F_{2i−2}, where y has no terms smaller than F_{2i+3}. If ℓ = 2i − 1, then similarly F_{k} + F_{ℓ} − F_{2i+1} = y + F_{2i} + F_{2i−1} = y + F_{2i+1}, and if ℓ < 2i − 1 then F_{k} + F_{ℓ} − F_{2i+1} = y + F_{2i} + F_{ℓ}. In these latter two cases the Zeckendorf representation of α is already clear, and z_{1}(α) = 2 which gives α ∈ A \ AB. In case ℓ = 2i, we may need to repeat the argument, in particular if F_{2i−2} belongs to the Zeckendorf representation of p, and possibly further repetition of this form will terminate with a representation of the form y + 2F_{2} = y + F_{3} with Zeckendorf indexes in y greater than 5. This is the unique case where z_{1}(α) is odd and hence α ∈ B. Any other case will give z_{1}(α) = 2 which gives α ∈ A \ AB.

Next, we find an i such that p − (F_{2i+1} − 1) ∈ B_{0} ⊕ 1. Take i = 1. We show that p − F_{3} ∈ B_{0}. Write p = a + F_{2} and show that a − F_{2} ∈ B_{0}, where z_{1}(a) = 2k ⩾ 4 is even, by the definition of the set AB and by a = p − 1. By the identity F_{2k} − F_{2} = F_{2k−1} + ⋯ + F_{3}, the result follows.

It remains to find an i such that α = p − (F_{2i+1} − 1) ∈ B_{0}. With a = p − 1, and since p+1 = a+F_{3}, we may define z_{1}(a) = F_{2k+2}, with k ⩾ 1. With the Zeckendorf representation a = y + F_{2k+2}, we must show that α = y + F_{2k+2} + F_{3} − F_{2i+1} ∈ B_{0}, for some i. If k > 1, then we let i = k; if k = 2, then α = y + F_{6} + F_{3} − F_{5} = y + F_{5}, so z_{1}(α) = 5 and otherwise z_{1}(α) = 3. If k = 1, then z_{1}(a + F_{3}) = 2ℓ + 1 > 3. In case a + F_{3} = F_{2ℓ+1}, then we choose i = ℓ, and so α = 0 ∈ B_{0}. Otherwise there is a smallest Zeckendorf term in y, say F_{m} > F_{5} > F_{2k+2}. Hence α = y′ + F_{m} + F_{5} − F_{2i+1}. If m is odd, we let i = (m − 1)/2, which gives z_{1}(α) = 5. Suppose m is even, then, if m ⩾ 8, we let 2i + 1 = m − 1, which gives either z_{1}(α) = 5 or, in case m = 8, z_{1}(α) = 7 (since the smallest Zeckendorf term in y′ is greater than m + 1 = 9).

Note that this example is also studied in Fox’s manuscript [2] but with a less elementary proof. The sequence of Sprague-Grundy values for the game S appears as sequence \underline{A242082} in OEIS.

3 Acknowledgements

Thanks to Carlos Santos for an enlightening discussion on the matter of nim-dimension.

References

[1] E. R. Berlekamp, J. H. Conway, R. K. Guy, Winning Ways for your Mathematical Plays, Volume 1, Academic Press, 1982.

[2] N. Fox, On aperiodic subtraction games with bounded nim sequence, preprint, 2014,

http://arxiv.org/abs/1407.2823.

[3] P. M. Grundy, Mathematics and games, Eureka 2 (1939), 6–8.

[4] C. Kimberling, Complementary equations and Wythoff sequences, J. Integer Sequences 11 (2008), Article 08.3.3.

[5] C. G. Lekkerkerker, Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci, Simon Stevin 29 (1952), 190–195.

[6] M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press, 2002.

[7] A. Ostrowski, Bemerkungen zur Theorie der Diophantischen Approximationen, Abh. Math. Sem. Hamburg 1 (1922), 77–98, 250–251.

[8] C. Santos, Some Notes on Impartial Games and Nim Dimension, PhD Thesis, University of Lisbon (2010).

[9] R. Silber, A Fibonacci property of Wythoff pairs, The Fibonacci Quarterly 14 (1976), 380–384.

[10] N. J. A. Sloane, The On-line Encyclopedia of Integer Sequences, http://www.oeis.org.

[11] R. P. Sprague, Über mathematische Kampfspiele, Tôhoku Mathematical Journal 41 (1935), 438–444. Electronically available at

https://www.jstage.jst.go.jp/article/tmj1911/41/0/41_0_438/_pdf.

[12] W. A. Wythoff, A modification of the game of Nim, Nieuw Arch. Wisk. 7 (1907) 199– 202.

[13] E. Zeckendorf, Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas. Bull. Soc. R. Sci. Liège 41 (1972), 179–182.

2010 Mathematics Subject Classification: Primary 91A46; Secondary 11B39. Keywords: subtraction game, Fibonacci number, Sprague-Grundy function.

(Concerned with sequences \underline{A000201}, \underline{A001950}, \underline{A003623}, \underline{A026352}, \underline{A089910}, and \underline{A242082}.)

Received April 9 2015; revised versions received July 14 2015; July 15 2015. Published in Journal of Integer Sequences, July 16 2015.

Return to Journal of Integer Sequences home page.