Stability for Take-Away Games

Simon Rubinstein-Salzedo Euler Circle Palo Alto, CA 94306 USA

                           simon@eulercircle.com

Sherry Sarkar College of Computing Georgia Institute of Technology Atlanta, GA 30332 USA

                            sherrys@gatech.edu

Abstract

In this paper, we study a family of take-away games called α-tag, parametrized by a real number α ≥ 1. We show that for any given α, there is a half-open interval I_{α} containing α such that the set of losing positions for α-tag is the same as the set of losing positions for β-tag if and only if β ∈ I_{α}. We then end with some results and conjectures on the nature of these intervals.

1 Introduction

In this paper, we study the losing positions of a certain family of games, known as take-away games. In our study, the games are indexed by a single parameter α, which is a real number greater than or equal to 1. It is also possible to study more general families of take-away games, as has been done by Zieve [14].

Here are the rules for the games we study. Let α ≥ 1 be a real number. We define α-tag (short for α-take-away game) to be the two-player game played with following rules:

1. The game begins with n stones in one pile, for some nonnegative integer n. A move in this game consists of removing at least one stone from the pile.

2. The two players alternate making moves.

3. The first player may take up to n − 1 stones.

4. After the first turn, a player can take up to α times the number of stones taken by the previous player on the last turn.

The winner of this game is the player who removes the last stone, or, more precisely, the loser is the player who is not able to remove a stone. (For instance, if n = 0 or n = 1, then the first player is not able to remove a stone, but the winner did not necessarily remove the last stone.)

Example 1. Below is an example of play in 3-tag. Red positions and arrows denote the first player’s moves, whereas blue positions and arrows denote the second player’s moves. As we shall see, the first player plays correctly in this game.

38→37→36→35→32→29→23→21→18→15→11→0

Since the game is symmetric in the two players, there are only two possible outcomes for α-tag, assuming optimal play: either the first player has a winning strategy, or the second player has a winning strategy. In accordance with standard combinatorial game theory parlance, we call a position in which the first player has a winning strategy an N position, and a position in which the second player has a winning strategy a P position.

There is a useful recursive way of determining which positions are N positions and which are P positions, thanks to the following lemma:

Lemma 2 ([1, Theorem 2.13]). A position is an N position iff there exists a move to a P position. A position is a P position iff all moves lead to N positions.

Studying any impartial combinatorial game like α-tag means determining which positions are the P positions and which are the N positions. Since in a typical game most positions are N positions, it is customary to focus on determining the smaller set of P positions. Formally, a position in α-tag consists of two pieces of information: the pile size (i.e., the number of stones remaining), and the move dynamic (i.e., the maximum number of stones that may be removed on the next turn). However, in the current work, we are solely interested in determining the outcome class (N or P) of the initial position, so we will be able to simplify our analysis by working only with the pile size, with a bit of care.

Definition 3. Let T (α) be the sequence of pile sizes n such that the only move a player can make to win α-tag in a pile of size n with optimal play is to remove all remaining stones.

We note, of course, that during game play, it may not be possible to remove all the stones from a pile of size n; whether that move is allowable or not depends on the last move played. We also note that T (α) consists of exactly those n such that the initial position of α-tag with n stones is a P position.

Example 4. For α = 2, we have 3 ∈ T (2), since if the first player tries removing only 1 or 2 stones, the next player wins by removing the remaining stones. The only winning strategy for the first player would be to remove all the stones. If we consider the game of 4 stones, the first player could remove 1 stone leaving the second player with 3 stones. As noted previously, the only way to win a game of 3 stones is to remove all 3, and the second player is restricted to removing at most 2. Therefore, we see that 4 ∉ T (2) since the first player can win with optimal play by playing some move other than removing all the stones.

Schwenk [8] showed that the sequence T (α) can be enumerated by a sequence which eventually satisfies a simple recurrence of the form P_{n} = P_{n−1} + P_{n−k} for some k, for sufficiently large values of n; see Theorem 12.

The main result in this paper is Theorem 23, which says that the sequences T (α) change in discrete intervals based on α. For instance, if 1 ≤ α < 2, then T (α) = (0, 1, 2, 4, 8, 16, …) consists of 0 together with the powers of 2. Similarly, when 2 ≤ α < \frac{5}{2}, then T (α) = (0, 1, 2, 3, 5, 8, 13, 21, …) consists of the Fibonacci numbers. We think of this as a stability theorem for take-away games: even though the rules and allowable moves in the game differ whenever we change α even slightly (for sufficiently large n), these extra options do not change the optimal outcomes of the game. Most of the paper is devoted to proving this theorem, and then we end with some further results and questions about the nature of these stable intervals.

2 History

One commonly studied game, first introduced by Whinihan [12], is the α = 2 version of the game described above, or better known as Fibonacci Nim. The T (α) positions for this game are the Fibonacci numbers. Fibonacci Nim is interesting because its winning strategy relies on the following theorem:

Theorem 5 (Zeckendorf, [6, 13]). Every positive integer can be uniquely expressed as the sum of pairwise nonconsecutive Fibonacci numbers.

Zeckendorf’s theorem together with the following lemma provides us with a winning strategy for Fibonacci Nim.

Lemma 6. For i ≥ 2, we have F_{i+1} ≤ 2F_{i} < F_{i+2}.

One can construct a winning strategy for any positive non-Fibonacci integer by combining Zeckendorf’s theorem with Lemma 6. Suppose that there are n stones. We look at the Zeckendorf representation of n, say

n = F_{i_{k}} + F_{i_{k−1}} + ⋯ + F_{i_{1}},

where for each j with 1 ≤ j ≤ k − 1 we have i_{j+1} − i_{j} ≥ 2. If k ≥ 2, then a winning strategy for the first player is to remove the smallest part of the Zeckendorf representation, i.e., F_{i_{1}}.

Due to Lemma 6, the second player will not be able to remove the entire next Zeckendorf part. Since all Fibonacci numbers are T (α) positions, the second player is forced to play essentially in the next term F_{i_{2}}, and lose in that part. We will see this line of reasoning again when we study the T (α) positions of the general α-tag.

Example 7. We illustrate an example of Player 1 executing the winning strategy with 12 stones. The Zeckendorf decomposition of 12 stones is

12 = 8 + 3 + 1.

Therefore, the winning play looks like the following

12→11→9→8→⋯

Note that the first player removes the smallest Zeckendort part, therefore forcing the second player to play (and lose) the game of 3 stones, the next smallest Zeckendorf part. This forces the second player to begin the game of 8 stones which is another T (α) position.

The nature of our results are similar to those of Fraenkel [4] on Wythoff’s game. Fraenkel also characterized the P positions of a parameter-based variant of Wythoff’s game with a recurrence and with an algebraic formula. More generally, the questions we answer here are reminiscent of those asked by Duchêne, Fraenkel, Nowakowski, Rigo, and Ho [3, 5]. The authors of those two papers study the modifications that can be made to the set of Wythoff’s game rules to keep the set of P positions constant.

3 P Positions of α-tag

In the previous section, we computed the sequence T (2) and showed that it is the sequence of Fibonacci numbers. Next, we consider the sequence T (α) for an arbitrary real number α ≥ 1. The computation of the sequence T (α) relies on a generalization of Zeckendorf’s theorem, first introduced by Schwenk [8]. Following Schwenk [8], we generate a sequence P^{α} as follows. Let the first two terms of P^{α} be P_{0}^{α} = 0, P_{1}^{α} = 1. Then define

P_{k+1}^{α} = P_{k}^{α} + P_{j}^{α},

where j is the the unique index such that

α · P_{j}^{α} ≥ P_{k}^{α} > α · P_{j−1}^{α}.

Example 8. The sequence P^{2} is the Fibonacci sequence, as is P^{2.4}. On the other hand, P^{2.5} is the sequence

1, 2, 3, 5, 7, 10, 15, 22, …

There is a generalization of Zeckendorf’s theorem based on the sequence P^{α}.

Theorem 9 (Generalized Zeckendorf theorem, [8]). Any positive integer n can be uniquely expressed as a sum of terms of the sequence P with the following condition

n = P_{i_{k}}^{α} + P_{i_{k−1}}^{α} + ⋯ + P_{i_{1}}^{α} where α · P_{i_{j}}^{α} < P_{i_{j+1}}^{α} for all j < k.

The proof is very similar to that of the classical Zeckendorf theorem.

Theorem 10 ([8]). For any α ≥ 1, the sequence T (α) is equal to the sequence (P_{i}^{α}).

The details of the proof can be found in Schwenk’s paper. The intuition, as described earlier, is that the winning strategy for α-tag is to remove the smallest generalized Zeckendorf part. From now on, we will refer to P_{i}^{α} instead of T (α) for this sequence. When α is fixed or clear from context, we shall simply write P_{i} instead of P_{i}^{α}.

Definition 11. The window W_{α}(P_{i}^{α}) of a term P_{i}^{α} is

W_{α}(P_{i}^{α}) = {P_{j}^{α} ∈ T (α) : α · P_{i−1}^{α} < P_{j}^{α} ≤ α · P_{i}^{α}}.

For some P = P_{i}^{α} ∈ T (α), the window W_{α}(P) is the set of Q = Q_{j}^{α} ∈ T (α) such that P + Q = Q_{j+1}^{α} is the next term in T (α). For P occurring early in the sequence T (α), W_{α}(P) may contain several elements. However, for sufficiently large values of P ∈ T (α), the W_{α}(P) consists of just a single element, and this is what causes the sequence of T (α) positions to satisfy a simple recurrence:

Theorem 12 ([8]). Fix α ≥ 1. Then there exists an integer k such that, for sufficiently large values of n, we have P_{n}^{α} = P_{n−1}^{α} + P_{n−k}^{α}.

Corollary 13. For n sufficiently large, W_{α}(P_{n}^{α}) is a set of size 1.

4 Lemmas about linear recurrences

In this section, we present some general lemmas about linear recurrences, as well as some about the specific family that are relevant to α-tag; we provide references to the literature when we were able to find other sources for them.

Definition 14. Let c_{0}, c_{1}, …, c_{k−1} ∈ ℂ. We say that a sequence of complex numbers a_{0}, a_{1}, … satisfies the eventual linear recurrence relation a_{n+k} = c_{k−1}a_{n+k−1} + c_{k−2}a_{n+k−2} + ⋯ + c_{0}a_{n} if the relation holds for all sufficiently large n.

Lemma 15. Let k be a positive integer, and let a_{0}, a_{1}, … be a sequence of complex numbers satisfying the eventual linear recurrence relation a_{n+k} = c_{k−1}a_{n+k−1} + c_{k−2}a_{n+k−2} + ⋯ + c_{0}a_{n} for all sufficiently large n. Let χ(x) = x^{k} −c_{k−1}x^{k−1} −c_{k−2}x^{k−2} −⋯−c_{0} be the characteristic polynomial of the eventual recurrence, and let r_{1}, …, r_{k} be its complex zeros, repeated with multiplicity. If all the r_{i}’s are distinct, then there exist β_{1}, …, β_{k} ∈ ℂ such that

a_{n} = β_{1}r_{1}^{n} + β_{2}r_{2}^{n} + ⋯ + β_{k}r_{k}^{n}

for all sufficiently large n.

See [11, Theorem 4.1.1] for a proof.

From now on, we shall arrange the r_{i}’s in decreasing order of magnitude: |r_{1}| ≥ |r_{2}| ≥ ⋯ ≥ |r_{k}|.

Lemma 16. With the notation of Lemma 15, suppose that all the r_{i}’s are distinct. Suppose furthermore that all the β_{i}’s are nonzero. If a_{n} > 0 for all sufficiently large n, then r_{1} is positive and real, r_{1} > |r_{2}|, and β_{1} > 0. We call r_{1} the positive dominant root.

See [2, Theorem 1] for a proof.

Lemma 17. With the notation of Lemma 15, suppose that all the r_{i}’s are distinct. Suppose also that the a_{i}’s are all integers. Suppose that χ(x) factors over ℚ as

χ(x) = χ_{1}(x)χ_{2}(x) ⋯ χ_{j}(x),

where each χ_{i}(x) is irreducible over ℚ. If r_{i_{1}}, …, r_{i_{d}} are the zeros of χ_{1}(x), then either β_{i_{1}} = β_{i_{2}} = ⋯ = β_{i_{d}} = 0, or else all of β_{i_{1}}, …, β_{i_{d}} are nonzero.

Proof. By [11, Proposition 4.2.2], the generating function for a_{n} has the form

∑_{n=0}^{∞} a_{n}x^{n} = R(x) + \frac{β_{i_{1}}}{1 − r_{i_{1}}x} + ⋯ + \frac{β_{i_{k}}}{1 − r_{i_{k}}x},

where R(x) ∈ ℚ(x). Let K be the Galois closure of ℚ(β_{i_{1}}, …, β_{i_{k}}, r_{i_{1}}, …, r_{i_{k}})(x) over ℚ(x), and let σ ∈ Gal(K/ℚ(x)) be an arbitrary element. Then σ permutes r_{i_{1}}, …, r_{i_{d}}, and since ∑_{n=0}^{∞} a_{n}x^{n} is fixed by σ, we must have

σ (\frac{β_{i_{1}}}{1 − r_{i_{1}}x}) = \frac{β_{i_{j}}}{1 − r_{i_{j}}x}

for some j with 1 ≤ j ≤ d. Furthermore, Gal(K/ℚ(x)) acts transitively on the terms \frac{β_{i_{j}}}{1−r_{i_{j}} x},

so for each j with 1 ≤ j ≤ d, there is some σ ∈ Gal(K/ℚ(x)) that sends \frac{β_{i_{1}}}{1−r_{i_{1}}x} to \frac{β_{i_{j}}}{1−r_{i_{j}} x}. Thus if β_{i_{1}} ≠ 0, then β_{i_{k}} ≠ 0 for 1 ≤ j ≤ d, and vice versa.

Lemma 18. For all k ≥ 2, k ≢ 5 (mod 6) the polynomial x^{k} − x^{k−1} − 1 is irreducible over ℚ. When k ≡ 5 (mod 6), then x^{k} −x^{k−1} −1 factors as x^{2} −x+1 times an irreducible factor.

Remark 19. Note that x^{2} − x + 1 = Φ_{6}(x) is the sixth cyclotomic polynomial, so its zeros are the primitive sixth roots of unity.

Proof. Selmer [9] shows that the polynomial f(x) = x^{k} −x−1 is irreducible for all k ≥ 2, and that g(x) = x^{k} + x + 1 is irreducible when k ≢ 2 (mod 3), and factors as x^{2} + x + 1 times an irreducible factor when k ≡ 2 (mod 3). When k is even, we have x^{k} −x^{k−1} −1 = −x^{k}f(−\frac{1}{x}), so it is irreducible. When k is odd, we have x^{k} −x^{k−1} −1 = x^{k}g(−\frac{1}{x}), so it is irreducible when k ≢ 5 (mod 6) and factors as x^{2} −x+1 times an irreducible factor when k ≡ 5 (mod 6).

Lemma 20. If k ≥ 2, then the polynomial x^{k} − x^{k−1} − 1 contains at most two zeros of any given absolute value.

Proof. Selmer [9] shows that on any circle |x| = r in the complex plane, the polynomials x^{k} ± (x + 1) have only at most two zeros. Since the zeros of x^{k} − x^{k−1} − 1 are the negative reciprocals of the zeros of x^{k} ± (x + 1) (depending on the parity of k), it follows that these polynomials also have at most two zeros on any given circle |x| = r.

Lemma 21. Let k ≥ 6. With notation as in Lemma 15, if a_{n} = a_{n−1}+a_{n−k} for all sufficiently large n, then |r_{2}| > 1, and r_{2} is nonreal.

Proof. First, note that r_{1} > 1, because the product of the zeros is equal to ±1, so some zero (and in particular the largest in absolute value) must have absolute value at least 1. Now suppose for some k ≥ 6, we have that |r_{2}| ≤ 1. We consider two cases: |r_{2}| = 1 and |r_{2}| < 1. Suppose first that |r_{2}| < 1. Then r_{1} is a Pisot number, i.e., a real algebraic integer greater than 1, all of whose Galois conjugates have absolute value less than 1. As shown in [10], the smallest Pisot number is the positive zero of x^{3} − x − 1, or 1.3247 . . .. However, for every k ≥ 6, 1.3^{k} − 1.3^{k−1} − 1 > 0 whereas 1^{k} − 1^{k−1} − 1 = −1 < 0, so 1 < r_{1} < 1.3. Thus r_{1} cannot be a Pisot number.

Suppose now that |r_{2}| = 1. If k ≡ 5 (mod 6), then Lemmas 18 and 20 imply that r_{2} and r_{3} are the primitive sixth roots of unity, and that |r_{4}| < 1. This means that r_{1} is again a Pisot number. However, this cannot be the case for the same reason as before, as r_{1} is smaller than the smallest Pisot number. On the other hand, if k ≢ 5 (mod 6) and |r_{2}| = 1, then r_{2} is a Galois conjugate of r_{1}, so r_{1} is a Salem number, i.e., an algebraic integer greater than 1 all of whose conjugates have absolute values at most 1, with at least one of the conjugates having an absolute value equal to 1. As shown in [7, §6], the minimal polynomial of any Salem number is a reciprocal polynomial, i.e., a polynomial p(x) such that p(x) = x^{deg(p)}p(\frac{1}{x}). Since x^{k} − x^{k−1} − 1 is not a reciprocal polynomial, r_{1} cannot be a Salem number. Thus |r_{2}| > 1 for all k ≥ 6.

Finally, we must show that r_{2} is nonreal. When k is odd, r_{1} is the only real zero of x^{k} − x^{k−1} − 1, so clearly r_{2} is nonreal. When k is even, x^{k} − x^{k−1} − 1 has two real zeros: the positive zero r_{1} and a negative zero. However, the negative zero lies between −1 and 0 and is thus not r_{2} for k ≥ 6, since |r_{2}| > 1.

Lemma 22. Let k ≥ 6. If a_{0}, a_{1}, a_{2}, … is a sequence of positive integers satisfying a_{n} = a_{n−1}+a_{n−k} for all sufficiently large n, then, with notation as in Lemma 15, r_{1} is real, β_{1} > 1, |r_{1}| > |r_{2}| = |r_{3}| > |r_{4}|, and β_{2}, β_{3} ≠ 0. Furthermore, β_{3} = β̄_{2}, where the bar denotes complex conjugation.

Proof. By Lemma 16 and the assumption that a_{n} is positive and satisfies the recurrence a_{n} = a_{n−1} + a_{n−k} for all sufficiently large n, it follows immediately r_{1} is real, β_{1} > 1, and |r_{1}| > |r_{2}|. Furthermore, r_{2} is nonreal by Lemma 21. Since nonreal zeros of polynomials with real coefficients come in complex conjugate pairs, it follows that the complex conjugate r̄_{2} of r_{2} is also a zero of x^{k} − x^{k−1} − 1. Thus |r_{2}| = |r_{3}|. By Lemma 20, |r_{2}| > |r_{4}|.

To see that β_{2}, β_{3} ≠ 0, note that all the zeros of χ(x), except possibly the two sixth roots of unity satisfying x^{2} − x + 1, have the same minimal polynomial over ℚ by Lemma 18. Since |r_{2}| > 1, r_{2} is not one of those roots of unity. Thus r_{1}, r_{2}, r_{3} are all zeros of the same irreducible factor of χ, and since β_{1} ≠ 0, Lemma 17 implies that β_{2}, β_{3} ≠ 0 as well.

To see that β_{3} = β̄_{2}, note that since Gal(ℂ(x)/ℝ(x)) = \{1, z ↦ z̄\} acts on the \frac{β_{i}}{1−r_{i}x}’s in the partial fraction decomposition of ∑_{n=0}^{∞} a_{n}x^{n} and complex conjugation sends r_{2} to r_{3}, it must send \frac{β_{2}}{1−r_{2}x} to \frac{β_{3}}{1−r_{3}x}. Thus β̄_{2} = β_{3}.

5 Stability

We now come to the main result of the paper.

Theorem 23. For any α ≥ 1, there exists a half-open interval I_{α} = [α_{0}, α_{1}) containing α such that for any β ∈ I_{α}, the sequence P_{i}^{β} is the same as the sequence P_{i}^{α}, and for all β ∉ I_{α}, the two sequences are not the same, in that there is some integer i for which P_{i}^{α} ≠ P_{i}^{β}.

Before we prove Theorem 23, let us take a look at why it ought to be true, by means of a typical example. Let us suppose that α = 3 and look at the sequence P_{n}^{3}. This sequence begins

P_{n}^{3} : 0, 1, 2, 3, 4, 6, 8, 11, 15, 21, 29, 40, 55, …,

with P_{n}^{3} = P_{n−1}^{3} + P_{n−4}^{3} for sufficiently large n. For example, P_{8}^{3} = 15. To compute P_{9}^{3}, we must add to P_{8}^{3} = 15 the unique P_{i}^{3} for which

3P_{i−1}^{3} < P_{8}^{3} ≤ 3P_{i}^{3},  (1)

which is 6. Thus P_{9}^{3} = 15 + 6 = 21. If we were to increase 3 to \frac{15}{4} and all the previous P-positions in \frac{15}{4}-tag agreed with those of 3-tag, then the left inequality in (1) with 3 replaced with \frac{15}{4}, namely

\frac{15}{4}Pi−1^{\frac{15}{4}} < P8^{\frac{15}{4}} ,

would fail since Pi−1^{\frac{15}{4}} = 4. Note that if we replace 3 with \frac{15}{4} − ε for any ε > 0 in the left inequality of (1), the inequality would still hold. Thus if all the P-positions of 3-tag and \frac{15}{4}-tag agree up to 15, then the next term is definitely different.

We can perform analogous calculations starting from any term of the sequence P_{n}^{3}. If α > 3, the only way that the sequence P_{n}^{α} could differ from P_{n}^{3} is if α is greater than the analogous ratio, starting with some term of P_{n}^{3}. In fact, one of these ratios is \frac{21}{6} = \frac{7}{2}, so the P-positions of α-tag are only equal to those of 3-tag when 3 ≤ α < \frac{7}{2}.

The proof of Theorem 23 is now reduced to showing that, for any α, the infimum of the sequence of such ratios is achieved. In particular, since all the ratios are greater than α, it follows that this infimum is strictly greater than α.

To this end, we introduce some notation for these ratios. Fix an α, and define a sequence Q_{k} = Q_{k}^{α} by setting

Q_{k}^{α} = \frac{P̂_{k}^{α}}{P_{k}^{α}} ,

where

P̂_{k}^{α} = min{P_{i}^{α} ∈ T (α) : P_{i}^{α} > max(W_{α}(P_{k}^{α}))}

is the smallest term in the sequence P_{i}^{α} greater than all the elements of the window of P_{k}^{α}. Alternatively, P̂_{k}^{α} = P_{j+1}^{α}, where P_{j}^{α} = max(W_{α}(P_{k})). As discussed above, the next β > α for which there exists an i such that P_{i}^{β} ≠ P_{i}^{α} is inf_{k}{Q_{k}^{α}}.

The following lemma will be key to proving Theorem 23.

Lemma 24. Let α ≥ 2 be a real number. The sequence Q_{n} = Q_{n}^{α} converges to some real number r_{1} > 1, and Q oscillates around the point of its convergence, in the sense that there are arbitrarily large integers n such that Q_{n} > r_{1}, as well as arbitrarily large integers n such that Q_{n} < r_{1}.

Proof. There is some positive integer k ≥ 2 such that the sequence P^{α} satisfies the linear recurrence of P_{n} = P_{n−1} + P_{n−k} for all sufficiently large k. When k ≤ 5, the remainder of the proof requires minor modifications since we cannot quite use Lemma 22, but most of it still works in that case as well. The cases k ≤ 5 can also be checked by hand if desired. When k = 2, r_{2} is real, so a slightly different argument must be made, but again, most of the proof still works. From now on, we will assume that k ≥ 6.

Since we are interested in the limiting or tail behavior of the sequence Q_{n}, we may ignore the initial terms, where P_{n} does not satisfy the eventual recurrence P_{n} = P_{n−1} + P_{n−k}. Let us consider the characteristic polynomial of the recurrence

χ(x) = x^{k} − x^{k−1} − 1,

and let the zeros of χ be r_{1}, r_{2}, r_{3}, …, r_{k}, where |r_{1}| > |r_{2}| ≥ ⋯ ≥ |r_{k}|. By Lemma 15, we know that there exist β_{1}, …, β_{k} ∈ ℂ such that

P_{n} = β_{1}r_{1}^{n} + β_{2}r_{2}^{n} + β_{3}r_{3}^{n} + ⋯ + β_{k}r_{k}^{n}

for all sufficiently large values of n. The sequence of ratios eventually converges to r_{1}^{k}. We want to know if the sequence of ratios oscillate below and above r_{1}^{k}. Thus, we study the sequence

\frac{P_{n+k}}{P_{n}} − r_{1}^{k}.

We have

\frac{P_{n+k}}{P_{n}} − r_{1}^{k} = \frac{r_{1}^{n+k} + \frac{β_{2}}{β_{1}} r_{2}^{n+k} + \frac{β_{3}}{β_{1}} r_{3}^{n+k} + ⋯ + \frac{β_{k}}{β_{1}} r_{k}^{n+k}}{r_{1}^{n} + \frac{β_{2}}{β_{1}} r_{2}^{n} + \frac{β_{3}}{β_{1}} r_{3}^{n} + ⋯ + \frac{β_{k}}{β_{1}} r_{k}^{n}} − r_{1}^{k}

= \frac{β_{2}r_{2}^{n}(r_{2}^{k} − r_{1}^{k}) + β_{3}r_{3}^{n}(r_{3}^{k} − r_{1}^{k}) + ⋯ + β_{k}r_{k}^{n}(r_{k}^{k} − r_{1}^{k})}{β_{1}r_{1}^{n} + β_{2}r_{2}^{n} + β_{3}r_{3}^{n} + ⋯ + β_{k}r_{k}^{n}}.

The denominator is positive since it is just equal to P_{n}. We must show that the numerator is positive for infinitely many n and negative for infinitely many n. Note that β_{i}, (r_{i}^{k} − r_{1}^{k}) are all constants; only r_{2}^{n}, r_{3}^{n}, …, r_{k}^{n} change as a function of n.

At this point, we are trying to determine if

β_{2}r_{2}^{n}(r_{2}^{k} − r_{1}^{k}) + β_{3}r_{3}^{n}(r_{3}^{k} − r_{1}^{k}) + ⋯ + β_{k}r_{k}^{n}(r_{k}^{k} − r_{1}^{k})  (2)

displays oscillatory behavior as a function of n. By Lemma 22, β_{2}, β_{3} ≠ 0 and |r_{3}| > |r_{4}|, so for sufficiently large values of n, r_{2}^{n} and r_{3}^{n} will dominate the rest of the terms, so for sufficiently large values of n, the sign of (2) will be the same as the sign of β_{2}r_{2}^{n}(r_{2}^{k} − r_{1}^{k}) + β_{3}r_{3}^{n}(r_{3}^{k} −r_{1}^{k}). Note that the behavior of terms r_{2} and r_{3}, the next zeros of largest magnitude, are what really determine the behavior of the entire sequence for sufficiently large n. Let us write

r_{2}^{k} − r_{1}^{k} = ρe^{iϕ}, r_{3}^{k} − r_{1}^{k} = ρe^{−iϕ}

and

r_{2} = re^{iθ}, r_{3} = re^{−iθ}.

Then we have

r_{2}^{n} = r^{n}e^{inθ}, r_{3}^{n} = r^{n}e^{−inθ}.

Thus we have

β_{2}r_{2}^{n}(r_{2}^{k} − r_{1}^{k}) + β_{3}r_{3}^{n}(r_{3}^{k} − r_{1}^{k}) = β_{2}r^{n}e^{inθ}ρe^{iϕ} + β_{3}r^{n}e^{−inθ}ρe^{−iϕ}.

Since β̄_{2} = β_{3} by Lemma 22, we may also write

β_{2} = se^{iψ}, β_{3} = se^{−iψ},

so that we have

β_{2}r_{2}^{n}(r_{2}^{k} − r_{1}^{k}) + β_{3}r_{3}^{n}(r_{3}^{k} − r_{1}^{k}) = 2sr^{n}ρ cos(ψ + nθ + ϕ).

Since ϕ, ψ, and θ are fixed and θ ≢ 0 (mod π), we know that cos(ψ + nθ + ϕ) is positive for infinitely many values of n and negative for infinitely many values of n. Thus there are infinitely many values of n for which Q_{n} > r_{1}, and infinitely many values of n for which Q_{n} < r_{1}, as desired.

Using Lemma 24, we can now prove Theorem 23.

Proof of Theorem 23. Define Q_{i}^{α} by

Q_{i}^{α} = \frac{P_{j+1}^{α}}{P_{i}^{α}}

where P_{j} = max(W_{α}(P_{i})). We established in Lemma 24 that Q^{α} has a minimum. Say we have some α < β < min(Q^{α}). We will show that P^{β} = P^{α}. Say P^{β} ≠ P^{α}. A sequence of T (α) positions is determined by

P_{i+1} = P_{i} + P_{j} if P_{j} ∈ W_{α}(P_{i}).

If P^{β} ≠ P^{α}, this implies there is a first occurrence of i such that W_{β}(P_{i}^{β}) ≠ W_{α}(P_{i}^{α}). Since β > α, this means that max(W_{β}(P_{i}^{β})) > max(W_{α}(P_{i}^{α})). Say P_{j} = max(W_{α}(P_{i}^{α})). Then max(W_{β}(P_{i}^{β})) ≥ P_{j+1}, which means

P_{j+1} ≤ β · P_{i},

or

Q_{i} = \frac{P_{j+1}}{P_{i}} ≤ β,

contrary to our assumption. Next, we show that if P^{β} = P^{α}, then β < min(Q^{α}). Say β ≥ min(Q^{α}). Let the index at which Q^{α} reaches its minimum be k. The sequence T (α) is determined by

P_{i+1} = P_{i} + P_{j} if P_{j} ∈ W_{α}(P_{i}).

We will show that max(W_{β}(P_{k}^{β})) > max(W_{α}(P_{k}^{α})). Let max(W_{α}(P_{k}^{α})) = P_{x}. Thus, min(Q^{α}) = \frac{P_{x+1}}{P_{k}}. Note that

αP_{k−1} < P_{x} ≤ α · P_{k}

and

P_{x} < P_{x+1} ≤ β · P_{k}.

Therefore, max(W_{β}(P_{k}^{β})) ≥ P_{x+1} > P_{x} = max(W_{α}(P_{k}^{α})). But since W_{β}(P_{k}^{β}) ≠ W_{α}(P_{k}^{α}), P^{β} ≠ P^{α}, which is a contradiction.

In short, the T (α) positions remain the same in certain intervals as α changes. Table 1 shows the first several stable intervals. Note that the same eventual recurrence can describe more than one set of T (α) positions, as seen with the recurrence P_{n} = P_{n−1} + P_{n−5}. This is because it takes longer for the recurrence to start holding when \frac{7}{2} ≤ α < \frac{11}{3} than it does when \frac{11}{3} ≤ α < \frac{43}{11}.

6 Cutoffs

Definition 25. A cutoff is some number α ≥ 1 such that, for any β < α, the sequences P_{n}^{α} and P_{n}^{β} are not identical.

In other words, the cutoffs are the endpoints of the stable intervals of Theorem 23. The first few cutoffs are 1, 2, \frac{5}{2}, 3, \frac{7}{2}, \frac{11}{3}, \frac{43}{11}, 4, \frac{13}{3}.

Range  Eventual recurrence  Initial conditions
1 ≤ α < 2 P_{n} = P_{n−1} + P_{n−1}  0,1
2 ≤ α < \frac{5}{2} P_{n} = P_{n−1} + P_{n−2}  0,1,2
\frac{5}{2} ≤ α < 3 P_{n} = P_{n−1} + P_{n−3}  0,1,2,3,5
3 ≤ α < \frac{7}{2} P_{n} = P_{n−1} + P_{n−4}  0,1,2,3,4,6
\frac{7}{2} ≤ α < \frac{11}{3} P_{n} = P_{n−1} + P_{n−5}  0,1,2,3,4,6,8,11,15,21
\frac{11}{3} ≤ α < \frac{43}{11} P_{n} = P_{n−1} + P_{n−5}  0,1,2,3,4,6,8,11
\frac{43}{11} ≤ α < 4 P_{n} = P_{n−1} + P_{n−6}  0,1,2,3,4,6,8,11,14,18,24,32,43
4 ≤ α < \frac{13}{3} P_{n} = P_{n−1} + P_{n−6}  0,1,2,3,4,5,7,9,12
\frac{13}{3} ≤ α < \frac{31}{7} P_{n} = P_{n−1} + P_{n−7} 0,1,2,3,4,5,7,9,12,15,19,24,31,40,52
\frac{31}{7} ≤ α < \frac{9}{2} P_{n} = P_{n−1} + P_{n−7}  0,1,2,3,4,5,7,9,12,15,19,24,31
\frac{9}{2} ≤ α < \frac{14}{3} P_{n} = P_{n−1} + P_{n−7}  0,1,2,3,4,5,7,9,11,14,18

Table 1: Stable intervals for α-tag

Remark 26. Before proving Theorem 23, it might be more natural to define a cutoff to be a number α ≥ 1 such that for any β < α and any γ > α, the sequences P_{n}^{β} and P_{n}^{γ} are not identical. Theorem 23 implies that these two definitions coincide, but later in this section we will see that it is possible to prove parts of the Theorem 23 in a simpler way but that does not guarantee that the two definitions match.

Corollary 27. All cutoffs are rational numbers.

Proof. The cutoffs are infima of sequences of rational numbers, and these infima are always achieved and hence rational.

In order to investigate the cutoffs more thoroughly, we consider a new sequence generated from the sequence P_{i}^{α}.

Definition 28. The sequence of indices of recurrence S_{i}^{α} is defined by

S_{i}^{α} = max{j : P_{i}^{α} + P_{i+j−1}^{α} = P_{i+j}^{α}}.

Example 29. Let α = \frac{7}{2}. Then we have the following initial values of P_{i} and S_{i}:

\begin{matrix}P_{i} & 1 & 2 & 3 & 4 & 6 & 8 & 11 & 15 & 21 & 27 & 35 & 46 & 61 \\ S_{i} & 3 & 4 & 4 & 4 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 \end{matrix}

Lemma 30 ([8]). For some α-tag, with T (α) positions P_{t}, if α · P_{i−1} < P_{j} ≤ α · P_{i}, then α · P_{i+1} ≥ P_{j+1}.

Lemma 31. For every i, we have S_{i}^{α} ≤ S_{i+1}^{α}.

Proof. Recall that the window W_{α}(P_{i}^{α}) of P_{i}^{α} ∈ T (α) is

W_{α}(P_{i}^{α}) = {P_{j}^{α} ∈ T (α) : P_{i}^{α} + P_{j}^{α} = P_{j+1}^{α} ∈ T (α)}.

We proved previously that

W_{α}(P_{i}^{α}) = {P_{j} ∈ T (α) : α · P_{i−1} < P_{j} ≤ α · P_{i}}.

Say P_{j} = max{W_{α}(P_{i}^{α})}. Since

α · P_{i−1} < P_{j} ≤ α · P_{i},

Lemma 30 implies that P_{j+1} ≤ α · P_{i+1}. Next, we prove that α · P_{i} < P_{j+1}. We prove this with contradiction. Assume P_{j+1} ≤ α · P_{i}. This would imply

α · P_{i−1} < P_{j} < P_{j+1} ≤ α · P_{i}.

This means P_{j+1} ∈ W_{α}(P_{i}^{α}). However, we said P_{j} = max{W_{α}(P_{i}^{α})} so this is a contradiction. Therefore, we have shown that

α · P_{i} < P_{j+1} ≤ α · P_{i+1}.

So, from assumption, P_{j} = max{W_{α}(P_{i}^{α})}, and Lemma 30 implies P_{j+1} ∈ W_{α}(P_{i+1}^{α}). Thus S_{i}^{α} = j − i − 1 and S_{i+1}^{α} ≥ j + 1 − (i + 1) − 1 = j − i − 1. Therefore, Lemma 30 implies that S^{α} is a monotonically increasing sequence.

Lemma 32 ([8]). Suppose there exists a j such that

P_{j+i+1} = P_{j+i} + P_{j+i−k}  (3)

for all i ∈ {0, 1, …, k + 1}. Then (3) holds for every nonnegative integer i.

Lemma 33. The number of cutoffs in any closed interval [a, b] is finite.

Proof. We first prove that the number of eventual recurrences in the interval is finite. There are at least two ways of doing this. One way would be to prove that the degree k of the eventual recurrence increases with α; this is true, but we have not proven it. An alternative approach is to use a result of Zieve [14]. Zieve proves that

\frac{log(α − 1)}{log(α) − log(α − 1)} ≤ k ≤ \frac{log(α)}{log(α + 1) − log(α)}.

It follows that for all α ∈ [a, b], we have

\frac{log(a − 1)}{log a − log (a − 1)} ≤ k ≤ \frac{log(b)}{log (b + 1) − log b}.

Since k is an integer, there are only finitely many eventual recurrences in a closed interval. Thus it remains to show that there are only finitely many sequences with the eventual recurrence P_{n} = P_{n−1} + P_{n−k}. From Lemma 31, we know that S^{α} is an increasing sequence. By Lemma 32, any positive integer m ≤ k can appear at most m + 1 times in the sequence S^{α}. Thus there are only finitely many possible initial strings of the sequence S^{α} before the sequence stabilizes at k. It follows that there are only finitely many cutoffs in any closed interval [a, b].

Remark 34. Lemma 33 almost gives us another proof of Theorem 23: it shows that the T (α) positions remain constant on intervals, except for a discrete set of exceptional points. However, we were not able to see how to use Lemma 33 to show that there are no exceptional points. Note that Definition 28 through Lemma 33 do not rely on the proof of Theorem 23.

Theorem 35. Every integer n ≥ 2 is a cutoff.

Proof. Let n ≥ 2 be an integer, let α be the last cutoff before n. The largest element of W_{α}(1) is ⌊α⌋ < n. Consider the sequence T (n) and W_{n}(1). The largest element of W_{n}(1) is n. Therefore, W_{n}(1) ≠ W_{α}(1). We assumed α to be the last cutoff before n. Thus, n is the next cutoff.

We can also prove a generalization of this theorem.

Theorem 36. Let x ≡ 0 (mod n!) and x > 0. Then x + \frac{1}{n} is a cutoff.

Before we prove Theorem 36, let us explain the intuitive reason behind it, which we make precise using windows. Let α be the largest cutoff before x+ \frac{1}{n}. Since all integers are cutoffs, we have α ≥ x. The sequence T (α) begins as an arithmetic progression with difference 1, then becomes an arithmetic progression with difference 2, then by 3, and so forth until it becomes an arithmetic progression with difference n:

0, 1, …, x, x + 1, x + 3, x + 5, …, 2x + 1, 2x + 4, …, 3x + 1, 3x + 5, …, nx + 1, nx + n + 2.

Recall that the next cutoff after α can be thought of as the minimum of Q_{i}^{α}. One of the elements of Q_{i}^{α} (which therefore upper bounds the next cutoff after α) is Q_{n} = \frac{nx+1}{n}.

Proof of Theorem 36. We proceed by induction on n, proving the given statement together with an auxiliary result that aids in the inductive step. The auxiliary result is that if α is the largest cutoff less than x+ \frac{1}{n}, then max(W_{α}(n)) = nx−n+1. For the original statement, the base case, n = 1, is simply Theorem 35. For the auxiliary statement, the largest cutoff less than x + 1 is simply x because the sequence T (α) begins 0, 1, 2, …, x + 1. The next term is x + 3. Thus max(W_{α}(1)) = x, as claimed.

Now suppose that the result is true for n, and we will prove it for n + 1. Let x ≡ 0 (mod (n + 1)!), and let α be the last cutoff before x + \frac{1}{n+1}. We consider the sequence T (α). Since x ≡ 0 (mod (n + 1)!), we also have x ≡ 0 (mod n!), so max(W_{α}(n)) = nx − n + 1. Since n + 1 ∈ T (α), the next term in T (α) after nx − n + 1 is in W_{α}(n + 1), and that

\begin{matrix}n & 2.5 & 3 & 3.5 & 4 & 4.5 & 5 & 5.5 & 6 & 10 & 20 & 30 & 40 & 75 \\ γ(n) & 3 & 4 & 5 & 8 & 11 & 14 & 18 & 21 & 74 & 424 & 1144 & 2100 & 9084 \end{matrix}

Table 2: Number of Cutoffs from 1 to n

next term is max(W_{α}(n)) + n = nx + 1. Let us now compute W_{α}(n + 1). It begins with nx + 1, and it is an arithmetic progression with common difference n + 1, so its elements are of the form nx + 1 + k(n + 1), where nx + 1 + k(n + 1) ∈ W_{α}(n + 1) if and only if nx + 1 + k(n + 1) ≤ α(n + 1). Since x ≤ α < x + \frac{1}{n+1}, we have nx + 1 + k(n + 1) ∈ W_{α}(n + 1) if and only if k < \frac{x}{n+1}, so

max(W_{α}(n + 1)) = nx + 1 + (\frac{x}{n + 1} − 1) (n + 1) = (n + 1)x − (n + 1) + 1,

completing the induction.

Theorem 36 show that for all integers d, there exists a cutoff whose denominator in lowest terms is d. In fact, it is quite common for rational numbers with small denominators to appear as cutoffs, even when they are not guaranteed by Theorem 36. For instance, all half-integers from \frac{5}{2} to \frac{29}{2} are cutoffs, but \frac{31}{2} is not. The next few half-integers that are not cutoffs are \frac{43}{2}, \frac{75}{2}, \frac{79}{2}, and \frac{95}{2}. It would be interesting to investigate the nature of the cutoffs with a given denominator. For example, for those arithmetic progressions of rational numbers such that Theorem 36 does not guarantee that all are cutoffs, is it true that infinitely many are cutoffs and infinitely many are not cutoffs? Or are there other arithmetic progressions containing only cutoffs or only noncutoffs (or all but finitely many cutoffs or noncutoffs)?

We have written a number of computer programs to aid the calculations of the sequences T (α) and the generation of cutoffs^{1}. Based on the data displayed in Table 2 and Figure 1, we make the following conjecture:

Conjecture 37. Let γ(n) be the number of cutoffs up to n. Then lim_{n→∞} \frac{γ(n)}{n^{2}} exists and is nonzero.

7 Acknowledgments

We would like to thank the referee for helpful suggestions.

References

[1] Michael Albert, Richard Nowakowski, and David Wolfe, Lessons in Play: an Introduction to Combinatorial Game Theory, CRC Press, 2007.

1Computer programs as well as cutoff data can be found at https://github.com/sherrysarkar.

Figure 1: γ(n) versus n

[2] John R. Burke and William A. Webb, Asymptotic behavior of linear recurrences, Fibonacci Quart. 19 (1981), 318–321.

[3] Eric Duchêne, Aviezri S. Fraenkel, Richard J. Nowakowski, and Michel Rigo, Extensions and restrictions of Wythoff’s game preserving its 𝒫 positions, J. Combin. Theory Ser. A 117 (2010), 545–567.

[4] Aviezri S. Fraenkel, How to beat your Wythoff games’ opponent on three fronts, Amer. Math. Monthly 89 (1982), 353–361.

[5] Nhan Bao Ho, Two variants of Wythoff’s game preserving its 𝒫-positions, J. Combin. Theory Ser. A 119 (2012), 1302–1314.

[6] Cornelis Gerrit Lekkerkerker, Representation of natural numbers as a sum of Fibonacci numbers, Simon Stevin 29 (1952), 190–195.

[7] Raphaël Salem, Power series with integral coefficients, Duke Math. J. 12 (1945), 153– 172.

[8] Allen J. Schwenk, Take-away games, Fibonacci Quart. 8 (1970), 225–234, 241.

[9] Ernst S. Selmer, On the irreducibility of certain trinomials, Math. Scand. 4 (1956), 287–302.

[10] Carl Ludwig Siegel, Algebraic integers whose conjugates lie in the unit circle, Duke Math. J. 11 (1944), 597–602.

[11] Richard P. Stanley, Enumerative Combinatorics. Volume 1, Vol. 49 of Cambridge Studies in Advanced Mathematics, Cambridge University Press, second edition, 2012.

[12] Michael J. Whinihan, Fibonacci Nim, Fibonacci Quart. 1 (1963), 9–13.

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

[14] Michael Zieve, Take-away games. In Games of No Chance (Berkeley, CA, 1994), Vol. 29 of Math. Sci. Res. Inst. Publ., pp. 351–361. Cambridge University Press, 1996.

2010 Mathematics Subject Classification: Primary 11B37; Secondary 91A46. Keywords: integer linear recurrence, combinatorial game.

(Concerned with sequences \underline{A002182}, \underline{A004394}, \underline{A040047}, \underline{A323256}, and \underline{A323257}.)

Received May 8 2019; revised versions received September 25 2019; October 2 2019. Published in Journal of Integer Sequences, January 1 2020.

Return to Journal of Integer Sequences home page.