Wythoff Nim Extensions and Splitting Sequences

Urban Larsson Mathematical Sciences Chalmers University of Technology and University of Gothenburg Göteborg Sweden

                urban.larsson@yahoo.se

Abstract

We study extensions of the classical impartial combinatorial game of Wythoff Nim. The games are played on two heaps of tokens, and have symmetric move options, so that, for any integers 0 ≤ x ≤ y, the outcome of the upper position (x, y) is identical to that of (y, x). First we prove that ϕ^{−1} = \frac{2}{1+\sqrt{5}} is a lower bound for the lower asymptotic density of the x-coordinates of a given game’s upper P-positions. The second result concerns a subfamily, called a Generalized Diagonal Wythoff Nim, recently introduced by Larsson. A certain split of P-positions, distributed in a number of so-called Pbeams, was conjectured for many such games. The term split here means that an infinite sector of upper positions is void of P-positions, but with infinitely many upper P-positions above and below it. By using the first result, we prove this conjecture for one of these games, called (1, 2)-GDWN, where a player moves as in Wythoff Nim, or instead chooses to remove a positive number of tokens from one heap and twice that number from the other.

1 Introduction

We study generalizations of the 2-player impartial take-away games 2-pile Nim [2], and Wythoff Nim [13]. A background on impartial (take-away) games can be found in the books [1, 3]. The literature on variations of Wythoff Nim is steadily increasing; for some further background, we refer to the papers [4, 5, 8, 9, 10, 11, 12]. We use standard terminology for the outcomes of such games without ties. A position is a previous-player win, a P-position, if none of its options is a P-position; otherwise it is a next-player win, an N-position. We follow the conventions of normal play, that is, a player who is not able to move loses. Thus, given an impartial game, we get a recursive characterization of the set of all P-positions beginning with the terminal position(s).

We let ℕ denote the positive integers and ℕ_{0} the non-negative integers. The game of 2-pile Nim is played on two piles of a finite number of tokens. A legal move consists of removing any positive number of tokens from exactly one pile, at most a whole pile. We represent a position by an ordered pair (x, y) ∈ ℕ_{0} × ℕ_{0}, denoting the number of tokens in the respective heaps. That is, the set of options from any position (x, y) is

Nim(x, y) = {(x − t, y) | x − t ≥ 0} ∪ {(x, y − t) | y − t ≥ 0}.

It is easy to see that the P-positions of this game are those where the pile heights are equal; the positions (x, x), for x ∈ ℕ_{0}, Bouton [2]. We regard these positions as an infinite P-beam of slope 1, with its source at the origin. See Figures 1 and 2.

In the game of Wythoff Nim a player moves as in Nim or instead removes the same number of tokens from both piles, at most the number in the smaller pile. Thus the set of options from any position (x, y) is

WN(x, y) = Nim(x, y) ∪ {(x − t, y − t) | x − t ≥ 0, y − t ≥ 0}.

Let

ϕ = \frac{\sqrt{5} + 1}{2}

denote the golden ratio. It is known, Wythoff [13], that a position of this game is P if and only if it belongs to the set

{(⌊ϕn⌋, ⌊ϕ^{2}n⌋), (⌊ϕ^{2}n⌋, ⌊ϕn⌋) | n ∈ ℕ_{0}};

see also Table 1. Thus, in the transformation from 2-pile Nim to Wythoff Nim, the single Nim-beam of P-positions has split into two distinct beams, with sources in the origin, and slopes 1/ϕ and ϕ respectively. The intuitive meaning of the term split is that there is an infinite sector, between two infinite regions of P-positions, which contains only N-positions. More formally, a sequence of pairs of natural numbers (x_{i}, y_{i}) splits, or (α, ϵ)-splits, if there are positive real numbers α and ϵ such that the set

\{i > n | α ≤ \frac{y_{i}}{x_{i}} ≤ α + ϵ\}

is empty, for n sufficiently large, and such that both

\{(x_{i}, y_{i}) | α > \frac{y_{i}}{x_{i}} \} ,

and

\{(x_{i}, y_{i}) | α + ϵ < \frac{y_{i}}{x_{i}} \}

are infinite.

Let p, q ∈ ℕ (with p < q). The game of Generalized Diagonal Wythoff Nim, (p, q)-GDWN [10], extends the rules of Wythoff Nim such that a player may instead remove pt tokens from either pile and qt tokens from the other, where t ∈ ℕ, provided that both heap sizes remain non-negative. (For given p and q we sometimes simply denote this game by GDWN.) That is, the set of options from any position (x, y) is

(p, q)-GDWN(x, y) = WN(x, y) ∪ {(x − pt, y − qt) | x − pt ≥ 0, y − qt ≥ 0}
∪ {(x − qt, y − pt) | x − qt ≥ 0, y − pt ≥ 0}.

See also Figure 1 for the rules of (1, 2)-GDWN and its first few P-positions. In Figure 2 we view the initial behavior of their respective P-beams.

Figure 1: The pictures illustrate typical move options (in gray) and initial P-positions of Nim, Wythoff Nim, and (1, 2)-GDWN respectively. The black square is a given game position. The white P’s represent the winning options from this position for the respective games. Hence the given position is N for each game. The lower left corner represents the terminal position (0, 0).

The motivation for this paper considers the splitting of Wythoff Nim’s P-beams for the case (1, 2)-GDWN; Section 3. In Section 4 we indicate why an analogous result holds also for (2, 3)-GDWN. Before this, in Section 2, we demonstrate a general result for certain extensions of Wythoff Nim. We show that the density ϕ^{−1}, obtained by projecting the upper P-positions of Wythoff Nim on the x-axis, suffices as a lower bound for the lower asymptotic density of similar projections, for any extension of Wythoff Nim. Let us begin by defining this general class of games.

Figure 2: These figures give the initial P-positions of the games Nim, Wythoff Nim and (1, 2)-GDWN. The left most figure illustrates 2-pile Nim’s single P-beam of slope 1. Then, in the middle we find Wythoff Nim’s pair of P-beams with slopes ϕ^{−1} and ϕ respectively and, at last, the initial P-positions of (1, 2)-GDWN, for all x-coordinates ≤ 50000. Experimental results from [10] indicate that the split of the upper P-positions “accumulate” on two lines of slope 1.477 ⋯ and 2.247 ⋯ respectively.

2 A density bound for Wythoff Nim extensions

An extension of Wythoff Nim, say G, has a set of options G(x, y) ⊇ WN(x, y), from each given position (x, y) ∈ ℕ_{0} × ℕ_{0}. The options are of the form (x − m_{1}, y − m_{2}) ∈ G(x, y), x ≥ x − m_{1} ≥ 0 and y ≥ y − m_{2} ≥ 0; not both m_{1} = m_{2} = 0, to disallow ties. We require that all options be symmetric, that is, (m_{1}, m_{2}) is a move from (x, y) if and only if (m_{2}, m_{1}) is a move from (y, x). Note that this is a relaxation of the traditional form of symmetric move options for variations of Wythoff Nim in the literature. We have chosen our symmetric variant, because it appears to be the weakest general form that guaranties symmetric Ppositions; that is (x, y) is P if and only if (y, x) is P. We also require that at most finitely many moves of the form (m_{1}, m_{2}), m_{1} > 0 and m_{2} > 0, have the same m_{1}-coordinate (m_{2}- coordinate) whenever moving from a fixed column (row). That is, given a column x > 0, the total number of non-Nim type options, from all positions of the form (x, y), is finite (and by symmetry, given a row y > 0, the total number of non-Nim type options, from all positions of the form (x, y), is finite). As we will see, in this way the new game will have so-called complementary sets (sequences) defining the P-positions.

Two sets of positive integers are complementary if each positive integer occurs in precisely one of these sets. A pair of sequences are complementary if they are complementary regarded as sets, and if there is no repetition within each sequence. The P-positions of Wythoff Nim are very well structured, in particular, the differences of coordinates are Δ_{n} := B_{n} − A_{n} = n, where A_{n} := ⌊ϕn⌋ and B_{n} := ⌊ϕ^{2}n⌋, for all n ∈ ℕ_{0}. We obviously get the density for the A-sequence as lim_{n∈ℕ} \frac{n}{A_{n}} = ϕ^{−1}. It is well known that the sequences defining Wythoff Nim’s non-terminal P-positions are complementary; see also Table 1. We will use this notation for Wythoff’s sequences throughout the paper.

\begin{matrix}B_{n} \\ A_{n} \\ n \\ Δ_{n} \\ 0 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ … \\ … \\ … \\ … \\ 0 \\ 1 \\ 3 \\ 4 \\ 6 \\ 8 \\ 9 \\ 0 \\ 2 \\ 5 \\ 7 \\ 10 \\ 13 \\ 15 \\ 0 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \end{matrix}

Table 1: Wythoff Nim’s unique terminal position is (A_{0}, B_{0}) = (0, 0). Its upper P-positions are (1, 2), …, (A_{n}, B_{n}), … and Δ_{n} = B_{n} − A_{n} = n for all n.

We code the upper P-positions of a given Wythoff Nim extension G by (a_{n}, b_{n}) where 0 < a_{n} < b_{n}, for all n > 0, and where the a-sequence is strictly increasing. By symmetry, G’s complete set of P-positions will be {(a_{i}, b_{i}), (b_{i}, a_{i}) | i ∈ ℕ} ∪ {(0, 0)}. We let δ_{i} := b_{i} − a_{i}, for all i. For convenience we denote the unique terminal position by (a_{0}, b_{0}) := (0, 0). That this is indeed the unique terminal position follows since all Nim-type moves are legal for any Wythoff extension.

\begin{matrix}b_{n} \\ a_{n} \\ n \\ δ_{n} \\ 0 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ … \\ … \\ … \\ … \\ 0 \\ 1 \\ 2 \\ 4 \\ 7 \\ 8 \\ 9 \\ 0 \\ 3 \\ 6 \\ 5 \\ 10 \\ 14 \\ 17 \\ 0 \\ 2 \\ 4 \\ 1 \\ 3 \\ 6 \\ 8 \end{matrix}

Table 2: These sequences constitute the first few P-positions of the Wythoff Nim extension (1, 2)-GDWN and δ_{i} = b_{i} − a_{i}, for all i. Note that the b-sequence is not increasing and hence neither the δ-sequence. It is not known whether all positive integers are represented in the latter sequence.

Proposition 1. The P-positions of any Wythoff Nim extension satisfy the following Property W: for all n ∈ ℕ, a_{n−1} < a_{n} and a_{n} < b_{n}; for all i ≠ j, δ_{i} ≠ δ_{j}, and the sequences a = (a_{i})_{i∈ℕ} and b = (b_{i})_{i∈ℕ} are complementary.

Proof. The inclusion G(x, y) ⊇ WN(x, y) implies that we can choose the a and b sequences such that a_{n−1} < a_{n}, a_{n} < b_{n} for all n > 0: the Nim-type moves give the first inequality and the diagonal type moves give the latter. Indeed, if there were a_{i}, a_{j} such that a_{i} = a_{j} and where b_{i} < b_{j}, then a Nim-type move would take (a_{j}, b_{j}) to (a_{i}, b_{i}), which is impossible, so all a_{i}’s have to be distinct. Neither can there be any index such that b_{n} = a_{n}, because then a diagonal type move would connect (0, 0) with (a_{n}, b_{n}). Hence it is clear that a_{n} < b_{n}, for all n, where we let positions of the form (a_{n}, b_{n}) represent the upper P-positions (and by symmetric rules of game, it follows that positions of the form (b_{n}, a_{n}) represent the lower P-positions). Further, we cannot have repetitions in the δ-sequence because this would connect two P-positions via a diagonal Wythoff type move. It remains to demonstrate that the sequences a and b are complementary. Symmetry and the inclusion of all Nim-type moves guarantee that there can be no repetitions of entries. That is, for each positive integer x, there is at most one index i such that a_{i} = x or b_{i} = x, but not both. Thus it suffices to demonstrate that, for each x, there is an index i such that either a_{i} = x or b_{i} = x. Let x be an arbitrary column. By the previous argument, there are at most x P-positions in the lower x − 1 columns (starting with x = 1 and the terminal P-position (0, 0)). Each such P-position is an option for at most finitely many game positions in the xth column, by the definition of a Wythoff extension. Hence, there is a least row y for which (x, y) does not have any P-position as an option. Then (x, y) is P. Hence there is at least one P-position in each column and so, by symmetry, a and b must be complementary.

\begin{matrix}b_{n} \\ a_{n} \\ n \\ δ_{n} \\ 0 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ … \\ … \\ … \\ … \\ 0 \\ 1 \\ 3 \\ 4 \\ 7 \\ 8 \\ 9 \\ 0 \\ 2 \\ 5 \\ 6 \\ 10 \\ 13 \\ 15 \\ 0 \\ 1 \\ 2 \\ 2 \\ 3 \\ 5 \\ 6 \end{matrix}

Table 3: These sequences do not correspond to the initial P-positions of any Wythoff Nim extension. Although the sequences do not contain any repetitions, they cannot correspond to such P-positions since δ_{2} = δ_{3} = 2. The table indicates the consequences of a given lower sequence growing too fast. The “7” in column 4 forces both “5” and “6” to reside in a lower column in the upper sequence. We study this type of behavior in our asymptotic result in Theorem 2.

For the other direction, one can see that any pair of sequences satisfying Property W constitute the P-positions of some Wythoff Nim extension. Namely, for each i, there are only finitely many positions of the form (a_{i}, y), with y < b_{i}. Therefore, at most b_{i} −1 extra moves need to be adjoined to Wythoff’s moves, for each i, to obtain a desired Wythoff extension. For example, we can include moves that take the (a_{i}, y)s to (0, 0), for all i. But we will not need this latter property in this paper. Note that, if we put an extra requirement that the move options be independent of the position moved from (apart from the non-negitivity condition of heap sizes), then it is easy to find counter examples to this converse statement. For example, upper P-positions beginning (1, 3), (2, 5), … will do. The reason that we do not require the move options to be independent of the positions moved from, is that the next result does not depend on it. On the other hand, the rules for the family of (p, q)-GDWN games are independent of the position moved from.

Theorem 2. Suppose that the sequences (a_{i}) and (b_{i}) satisfy Property W as defined in Proposition 1. Then, for n ∈ ℕ,

\frac{#\{i > 0 | a_{i} < n\}}{n} ≥ ϕ^{−1} − o(1)  (1)

and

\frac{#\{i > 0 | b_{i} < n\}}{n} ≤ ϕ^{−2} + o(1).  (2)

In particular the result holds for {(a_{i}, b_{i})} representing the upper P-positions of any Wythoff Nim extension.

Proof. For any given Wythoff Nim Extension, define the y-sequence as the unique permutation of the b-sequence with entries in increasing order. That is y_{n} < y_{n+1} for all n and {y_{n}} = {b_{n}}. Define the unique surjective function j : ℕ → ℕ, j = j(n) such that, for all n, a_{j} ≤ n < a_{j+1}. (This is well defined by (a_{i}) strictly increasing and a_{1} = 1.) Suppose that (1) does not hold. Then, by (a_{i}) increasing, there is an ϵ′ > 0 such that, for all sufficiently large n, \frac{j(n)}{a_{j(n)}} < ϕ^{−1} − ϵ′. By inverting this equation, we obviously get \frac{1}{ϕ^{−1}−ϵ′} < \frac{a_{j(n)}}{j(n)} , which implies that there is an ϵ > 0 such that, for all sufficiently large n, ϕn+ \frac{ϵn}{2} < a_{n}. By complementarity this implies, for all sufficiently large n, ϕ^{2}n − γ(ϵ) ≥ y_{n}, where γ(ϵ) > \frac{ϵn}{2} is a function of ϵ only. Thus

δ′_{n} := y_{n} − a_{n}
< (ϕ^{2} − ϕ)n − ϵn
= (1 − ϵ)n,  (3)

for all sufficiently large n. Hence, since all entries in the sequence (δ′_{n})_{n≤N} are positive integers, it must contain at least ϵN (pairwise) repetitions, for all sufficiently large N.

Given C ∈ ℕ, define the finite set S_{b} = S_{b}(C), by x ∈ S_{b} if and only if b_{x} ≤ C. That is S_{b} contains the indices of all b-entries smaller than C. For a given C, let (n_{i}) be the unique increasing sequence of the numbers in S_{b}. Then, clearly n_{i} ≥ i, for all i, and therefore also, by (a_{i}) increasing, a_{n_{i}} ≥ a_{i}, for all i. Suppose now that N is sufficiently large, so that (δ′_{n})_{n≤N} contains ϵN repetitions, as defined in the previous paragraph, and study the unique set S_{b} of size N. It contains the indices of the N smallest entries in the b-sequence, (n_{i})_{i=1}^{N}. Thus, since ∑_{S_{b}} a_{i} ≥ ∑_{i=1}^{N} a_{i} and ∑_{S_{b}} b_{i} = ∑_{i=1}^{N} y_{i}, we get ∑_{S_{b}} δ_{i} ≤ ∑_{i=1}^{N} δ′_{i}, and so the sequence (δ_{i})_{i=1}^{N} must also contain at least ϵN repetitions for all sufficiently large N. This contradicts property W, and so (1) must hold and thus, by complementarity also (2).

3 Splitting P-positions for (1, 2)-GDWN

In this section we analyze the game (1, 2)-GDWN from paper [10] and prove that its upper P-positions (2, 0.05)-split. The following lemma shows that it suffices to establish a positive lower asymptotic density for x-coordinates of P-positions above the line y = 2x.

Lemma 3. Suppose that there is a positive lower asymptotic density of x-coordinates of P-positions above the line y = 2x. Then, the upper P-positions {(a_{n}, b_{n}) | n ∈ ℕ_{0}}, of (1, 2)-GDWN, split.

Proof. Let (k_{i}) denote the unique increasing sequence of indices such that, for all i ∈ ℕ, 2 < b_{k_{i}}/a_{k_{i}} and if k_{i} < j < k_{i+1} then b_{j}/a_{j} < 2 (put k_{0} = 0). Already in paper [10] we proved that (k_{i}) is infinite. Further it was demonstrated that, by a ‘greedy’ choice, the b-sequence satisfies, for all i,

b_{k_{i+1}} = 2(a_{k_{i+1}} − a_{k_{i}}) + b_{k_{i}} + 1.  (4)

The assumption is that there is an ϵ > 0 such that, for all sufficiently large N,

#{i | a_{k_{i}} < N} ≥ ϵN.  (5)

It suffices to show that, for all sufficiently large N, the set

{(N, 2N), (N, 2N + 1), …, (N, (2 + ϵ)N)}  (6)

will contain only N-positions (assuming that ϵN is an integer). We use induction with base case: there is a move from (N, 2N) to (0, 0). Further, the induction hypothesis is that there is a move from (N, 2N + x) to (a_{k_{i}}, b_{k_{i}}), x ∈ ℕ_{0} of the form: 2N + x − b_{k_{i}} = 2t and N − a_{k_{i}} = t, t ∈ ℕ. By (5), it suffices to show that there is a move from (N, 2N + x + 1) to (a_{k_{i+1}}, b_{k_{i+1}}). By eliminating t, we get 2N +x+1−b_{k_{i}} = 2(N −a_{k_{i}})+1 which, by (4) becomes 2N + x + 1 − b_{k_{i+1}} = 2(N − a_{k_{i+1}}). Thus, the P-positions of the form in (4) contribute at least ϵN consecutive N-positions above the line y = 2x, for each x-coordinate x = N, as described in (6). These N-positions separate the infinite sequence of P-positions of the form (a_{k_{i}}, b_{k_{i}}) from the other ones. By [10] we know that there are infinitely many P-positions (a_{n}, b_{n}) satisfying 1 ≤ \frac{b_{n}}{a_{n}} ≤ 2. Hence, given the assumptions, each requirement for a split is satisfied.

Lemma 4. For any p, q ∈ ℕ, (p, q)-GDWN is a Wythoff extension.

Proof. Obvious.

Theorem 5. The upper P-positions {(a_{n}, b_{n}) | n ∈ ℕ_{0}} of (1, 2)-GDWN split.

Proof. If there is a positive lower density of P-positions above the line y = 2x then, by Lemma 3 the result holds.

Assume for a contradiction that there are at most o(N) P-positions above the line y = 2x with x-coordinate less than N. Then almost all upper P-positions lie in the sector defined by the lines y = x and y = 2x. By Lemma 4 and Theorem 2, the number of upper P-positions with x-coordinate less than N is at least ϕ^{−1}N − o(N).

We denote by

τ = τ(N) := \frac{#\{i | a_{i} ≤ N\}}{N}

and observe that τ > ϕ^{−1} − o(1).

By Theorem 2, for all sufficiently large N, the number of N-beams of slope 1, which intersect the (red) dashed line in Figure 3 between y = N and y = \frac{3N}{2} , and originating from P-positions in region

(I) is at least τ \frac{N}{2} ,

(II) is at least cτ \frac{N}{2} , where 0 < c < 1 is some real constant.

Similarly, the number of N-beams of slope 2, which intersect the (red) dashed line between y = \frac{3N}{2} and y = 2N, originating from P-positions in region

(I) is at least τ \frac{N}{2} ,

(III) is at least (1 − c)τ \frac{N}{2} , where 0 < c < 1 is the real constant from (II),

(IV) is at least (1 − τ)\frac{N}{3} ,

where the last item is by complementarity of the a and b sequences. Hence, the number of N-beams of slope 1, from regions I and II, is at least

(1 + c)\frac{τN}{2} .

The number of N-beams of slope 2, from regions I, III and IV, is at least

(\frac{τ}{2} + (1 − c)\frac{τ}{2} + (1 − τ)\frac{1}{3}) N.

From these expressions we see that the constant c does not affect the total number of Nbeams. Hence we omit it and, by τ ≥ ϕ^{−1} − o(1), get that the total number of N-beams is at least N \frac{7ϕ^{−1}+2}{6} > 1.05N, which contradicts the definition of N and P, namely it implies that either there are two P-positions on the same line of slope 2 or there are two P-positions on the same line of slope 1.

\begin{matrix}y \\ x \end{matrix} ; I ; II ; II ; III ; IV ; N ; N/2 ; N/3 ; (N, N) ; (N, 3N/2) ; (N, 2N) ; (N/2, N/2) ; (N/3, N/6)

Figure 3: We consider P-positions in four regions sending N-positions to lattice points with x-coordinate N. The ones from region I and II have slope 1 and the ones from region I, III and IV have slope 2. The y-coordinate 3N/2 is pivotal in our argument. Below it we count the beams of slope 1 and above it the beams of slope 2.

4 The game (2, 3)-GDWN

By an analogous method one can also prove that the upper P-positions of (2, 3)-GDWN split. Some extra care is needed for the treatment of the P-positions above the line of slope 3/2, but one can see that the packing of the N-beams originating from P-positions above this line will be dense also for this game; within an O(N) distance to the y-coordinate 3N/2 (with N even), although they will not be strictly “greedy” as for (1, 2)-GDWN. Another slight complication is that one needs to regard two columns, N, N + 1 for this game, rather than the single N-column in (1, 2)-GDWN. However this still implies that the number of positions to check for its N-status, between this line and the one of slope 1, is N. Further, the contribution from analogues of regions I, II and III in Figure 3 gives the same estimate as for (1, 2)-GDWN. By Theorem 2 and by inspection, for this case the contribution from region IV gives an additional number of P-positions below x-coordinate 3N/10; there are at least 3(1 − τ)N/10 of them. Hence the total number is at least (\frac{6τ}{5} + \frac{3}{10})N > 1.04N.

Theorem 6. The upper P-positions {(a_{n}, b_{n}) | n ∈ ℕ_{0}} of (2, 3)-GDWN split.

For other variations of GDWN the analysis seems more technical and new ideas may be needed. In particular, for such games, various log-period behaviors of diverging P-beams are observed in the paper [10], as does not appear to be the case for (1,2)-GDWN and (2,3)-GDWN.

5 Discussion and questions

The final question in the thesis [7] concerns an analog to Property W (as defined in Proposition 1) for general permutations. Let us restate it: is there any permutation g on the natural numbers such that g(x) − x ≠ g(y) − y whenever x ≠ y and such that

lim sup_{i→∞} \frac{g(i)}{i} − lim inf_{i→∞} \frac{g(i)}{i} < 1?

In this paper we have provided a negative answer in case g is an involution. The question remains open for general permutations.

Via Theorem 2, Property W in fact implies a property for a given set S of positive integers as follows. Let {s_{i}} = S ⊂ ℕ, with the s_{i}’s distinct (and in increasing order). We have demonstrated that, if there is an ordering (t_{i}) of the numbers in ℕ \ S such that t_{i} − s_{i} = t_{j} − s_{j} > 0 implies i = j, then the lower asymptotic density of S must be greater than or equal to ϕ^{−1}.

The converse does not hold in general. For example any set S beginning as the a-sequence in Table 3 does not have this property, but it can easily be constructed to have lower density greater than or equal to ϕ^{−1}, for example, by letting it converge to Wythoff’s A-sequence. This converse question is more meaningful in the game’s setting. For example, one would like to classify those restrictions of Wythoff Nim that satisfy (1). Does the removal of finitely many diagonal moves from Wythoff Nim change this property? Then there will be repetitions in the δ-sequence, even occurrences a_{i} = b_{i}, so we have to relax property W as appropriate.

A sequence (x_{i}, y_{i}) density-splits if it (α, ϵ)-splits and each of the sets \{x_{i} | α ≥ \frac{y_{i}}{x_{i}} \} and \{x_{i} | α + ϵ ≤ \frac{y_{i}}{x_{i}} \} has a positive lower asymptotic density. Do our results hold if we exchange split for density-split everywhere? We conjecture a positive answer, but some details are still missing for the upper P-positions’ lower P-beam, see paper [10].

6 Acknowledgements

I would like to thank the anonymous referee for many helpful comments.

References

[1] E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways, Vols. 1–2, Academic Press, 1982. Second edition, Vols. 1–4, A. K. Peters, 2001–2004.

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

[3] J. H. Conway, On Numbers and Games, Academic Press, 1976. Second edition, A. K.Peters, 2001.

[4] E. Duchêne, A. S. Fraenkel, R. J. Nowakowski, and M. Rigo, Extensions and restrictions of Wythoff’s game preserving its P-positions. J. Combinat. Theory Ser. A 117 (2010), 545–567.

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

[6] P. Hegarty and U. Larsson, Permutations of the natural numbers with prescribed difference multisets, Integers 6 (2006), #A3.

[7] J. Knape and U. Larsson, Sets of integers and permutations avoiding solutions to linear equations, Master’s thesis, University of Göteborg, 2004.

[8] U. Larsson, 2-pile Nim with a restricted number of move-size imitations. With an appendix by Peter Hegarty. Integers 9 (2009), #G04, 671–690.

[9] U. Larsson, Blocking Wythoff Nim, Electron. J. Combin. 18 (2011), Paper 120.

[10] U. Larsson, A Generalized Diagonal Wythoff Nim, Integers 12 (2012), #G02.

[11] U. Larsson, Restrictions of m-Wythoff Nim and p-complementary Beatty sequences, to appear in Games of No Chance 4.

[12] U. Larsson and J. Wästlund, Maharaja Nim: when Wythoff’s Queen meets the Knight, preprint submitted to Integers.

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

2010 Mathematics Subject Classification: Primary 91A46; Secondary 11B75. Keywords: combinatorial game, complementary sequence, golden ratio, impartial game, integer sequence, lower asymptotic density, splitting sequence, Wythoff Nim.

Received September 18 2012; revised versions received November 22 2013; January 6 2014; February 18 2014; March 10 2014; April 3 2014. Published in Journal of Integer Sequences, April 4 2014.

Return to Journal of Integer Sequences home page.