INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 4 (2004), #G03

PILESIZE DYNAMIC ONE-PILE NIM AND BEATTY’S THEOREM

Arthur Holshouser

3600 Bullard St., Charlotte, NC 28208, USA

Harold Reiter

Department of Mathematics, University of North Carolina Charlotte, Charlotte, NC 28223, USA

                         hbreiter@email.uncc.edu

James Rudzinski

Department of Mathematics, Emory University, Atlanta, GA 30322, USA

                           jerudzin@yahoo.com

Received: 12/16/03, Revised: 5/20/04, Accepted: 5/26/04, Published: 5/31/04

Abstract

In [4] we proved a generalization of Beatty’s Theorem which we stated came from the Nim value analysis of a game. In this paper we give the Nim value analysis of this game and show its relationship with Beatty’s Theorem. The game is a one-pile counter pickup game for which the maximum number of counters that can be removed on each successive move changes during the play of the game. The move size is bounded by a move function f whose arguments are pile sizes. After analyzing this game, we discuss a blocking version of this game as well as the misère version.

1. Introduction

Two players alternately remove a positive number of counters from a pile of counters. The maximum size of the move is determined by a move function f : N → N whose arguments are pile sizes. Each player in his turn must remove from one up to the minimum of n and f(n) counters, where n is the size of the pile. The game ends when either the pile is empty or f(n) = 0 and the winner is the last player to move. Since we can replace a move function f(n) with min(n, f(n)) without changing the legal moves in the game, without loss of generality we will assume 0 ≤ f(n) ≤ n throughout the paper. Our analysis solves a very large class of games that includes as a subclass all games whose move function satisfies both

1. f(0) = 0 and

2. For all n ≥ 0, f(n + 1) − f(n) ∈ {0, 1}.

The second condition, called the unit jump condition (ujc), will be used repeatedly.

The move functions f(n) = ⌊rn⌋ and f(n) = ⌈rn⌉ for some r, 0 < r ≤ 1, are primitive special cases. Our analysis using f(n) = n solves both the regular and misère versions of m-pile Bouton’s nim. Also, our analysis using f(n) = min(n, k), k = 1, 2, … solves both the regular and misère versions of m-pile modular Bouton’s nim.

At the end of this paper, we will show how to generate numerous examples of the game. These will include the ‘primitive’ move functions f(n) = ⌊rn⌋ and f(n) = ⌈rn⌉, 0 < r ≤ 1. In Example 1 immediately after Lemma 6, we show how the analysis in this paper also generalizes Beatty’s Theorem. In a companion paper [4], we used the same basic analysis as we do here to extend Beatty’s Theorem to strictly increasing continuous functions that are independent. See [1] and [6]. Also, a further extension of this paper led us to discover a class of combinatorial games that we have not seen in the literature. We call these blocking games, and we discuss the blocking version of this game briefly in Section 6. See [2].

This paper uses the Sprague-Grundy theory of combinatorial games which we summarize below. The Grundy values of positions, which we denote g(n), are called Nim values in this paper. Sections 2 and 3 can be omitted by those readers who are familiar with this material.

2. Beatty’s Theorem

In 1926 Sam Beatty made the following discovery, which he posed as a problem in [1]. If a is a positive irrational number, the sequences m(1+a), m = 1, 2, … and n(1+a^{−1}), n = 1, 2, … together contain exactly one number from each of the intervals (k, k + 1), k = 1, 2, . . ..

3. Impartial Games

Our game is a finite, impartial game played under the usual rules of play:

1. two players alternate moving,

2. there is no infinite sequence of moves,

3. both players have the same moves available, and

4. the winner is the last player to make a move.

Such a game can be thought of a directed acyclic graph. Each vertex of the graph corresponds to a position in the game, and the directed edges correspond to the possible moves. The followers of a vertex are those positions joined by an outgoing edge.

The minimum excluded value (mex) of a finite set of nonnegative integers is the least nonnegative integer not in the set. For example, mex{1, 2, 4, 0} = 3 and mex{ } = 0. The Nim value of a position is the mex of the nim values of its followers. A position with no followers (a terminal position) has Nim value 0. It is easy to see that the winning strategy is to move to a position with Nim value 0, for then the opponent either has no move at all and loses immediately, or must move to a position with Nim value greater than 0, and so must eventually lose.

Nim values are of greatest use in composite games where there are several components. Each player, on his turn, selects a component game in which a legal move can be made and makes a legal move in that game. The game is over when no legal moves can be made in any of the component games, and the winner is the player who makes the last move. The Nim value of the composite game is the nim sum ⊕ of the Nim values of the component games. The nim sum is obtained by writing the integers in binary and adding modulo 2 without carrying. For example, 2 ⊕ 3 = 10_{2} ⊕ 11_{2} = 01_{2} = 1.

The positions (P_{1}, P_{2}, …, P_{k}) with a nim sum of zero (g(P_{1})⊕g(P_{2})⊕…⊕g(P_{k}) = 0) are called balanced positions, and the positions with a non-zero nim sum are called unbalanced. A player who moves from an unbalanced position can always move to a balanced position, but a player who moves from a balanced position must always move to an unbalanced position. Note that all terminal positions are balanced. The misère version of the game is played under the same rules except that the loser is the last player to make a move. Let us call a component game G_{i} special if for each non-terminal position P in G_{i} such that g(P) = 0, there is a follower Q of P with g(Q) = 1. If each component G_{i} is special, then the balanced positions (P_{1}, P_{2}, …, P_{k}) in the misère version of the composite game are given by the following two conditions:

1. If at least one g(P_{i}) ≥ 2, then (P_{1}, P_{2}, …, P_{k}) is balanced if and only if g(P_{1}) ⊕ g(P_{2}) ⊕ … ⊕ g(P_{k}) = 0.

2. If each g(P_{i}) ∈ {0, 1}, then (P_{1}, P_{2}, …, P_{k}) is balanced if and only if g(P_{1})⊕g(P_{2})⊕ … ⊕ g(P_{k}) = 1.

All the other positions are unbalanced. Note that all the terminal positions are unbalanced. We point out later that all of the games studied in this paper are special.

4. Main Theorems

We now proceed to solve the subclass of games mentioned above. This is followed by an extension of the solution to the entire class of games. Let N denote the set of non-negative integers and Z the set of all integers.

Theorem 1. Let n be a non-negative integer. Consider the game (n, f) where n is the pile size and f : N → N is a move function such that f(0) = 0 and f satisfies the ujc. Then the Nim values g(n) in the game (n, f) satisfy the following:

1. g(0) = 0

2. If f(n) − f(n − 1) = 1 and n ≥ 1, then g(n) = f(n).

3. If f(n) − f(n − 1) = 0 and n ≥ 1, then g(n) = g(n − 1 − f(n)).

4. For all non-negative integers n, {g(n), g(n − 1), …, g(n − f(n))} = {0, 1, 2, …, f(n)}, where 0 < 1 < … < f(n) (that is, the elements of the set {0, 1, 2, …, f(n)} are listed exactly once).

5. For all non-negative integers n, g(n) ≤ f(n).

Proof. As noted above, f(n) ≤ n for all n ∈ N. The proof of the theorem is by mathematical induction on n. Starting the induction at n = 0 is trivial because only conditions 1, 4 and 5 apply, which hold because g(0) = f(0) = 0. Now assume that the theorem holds for k ∈ {0, 1, 2, …, n − 1}. We show that the statements also hold for n. Since f satisfies ujc, either Case 1. f(n − 1) + 1 = f(n) or Case 2. f(n − 1) = f(n). We will tacitly assume that f(n) > 0. If f(n) = 0, then f(0) = f(1) = f(2) = … = f(n) = 0 since f is non-decreasing. Proof for case 1. The condition can be rewritten as f(n)−f(n−1) = 1. Thus we need to prove condition 2. Once we prove condition 2, it is clear that condition 5 also holds. From condition 4 and the induction hypothesis, {g(n − 1), g(n − 2), …, g(n − 1 − f(n − 1))} = {0, 1, 2, …, f(n − 1)}, where 0 < 1 < ⋯ < f(n − 1). Then from the definition of Nim value,

g(n) = mex({g(n − 1), g(n − 2), …, g(n − f(n))})
= mex({g(n − 1), g(n − 2), …, g(n − 1 − f(n − 1))})
= mex({0, 1, 2 …, f(n − 1)} = f(n − 1) + 1 = f(n).

To prove condition 4, note that

{g(n), g(n − 1), g(n − 2), …, g(n − f(n))}
= {g(n), g(n − 1), …, g(n − 1 − f(n − 1))}
= {g(n)} ∪ {g(n − 1), g(n − 2), …, g(n − 1 − f(n − 1))}
= {f(n)} ∪ {0, 1, 2, …, f(n − 1)}
= {0, 1, 2, …, f(n)}, where 0 < 1 < ⋯ < f(n),

since 0 < 1 < … < f(n − 1) and f(n − 1) < f(n).

Proof for case 2. We are given f(n − 1) = f(n). Thus we need to show condition 3, namely, g(n) = g(n − f(n) − 1). First we need to make sure that n − f(n) − 1 ≥ 0. But 0 ≤ f(n − 1) ≤ n − 1 was assumed previously and from f(n − 1) ≤ n − 1 and f(n) = f(n − 1), it follows that n − f(n) − 1 ≥ 0. The induction hypothesis gives {g(n − 1), g(n − 2), …, g(n − 1 − f(n − 1))} = {0, 1, 2, … f(n − 1)} where 0 < 1 < ⋯ < f(n − 1). Therefore,

g(n) = mex({g(n − 1), g(n − 2), …, g(n − f(n))})
= mex({g(n − 1), g(n − 2), …, g(n − f(n − 1))})
= mex({g(n − 1), g(n − 2), …, g(n − 1 − f(n − 1))}\{g(n − 1 − f(n − 1))})
= mex({0, 1, 2, … f(n − 1)}\{g(n − 1 − f(n − 1))}),
= g(n − 1 − f(n − 1)) = g(n − 1 − f(n)) (from the definition of mex),

which proves condition 3.

Next note that g(n) = g(n − f(n) − 1) ≤ f(n − f(n) − 1) ≤ f(n) by the induction hypothesis with condition 5 and the fact that f is non-decreasing. So condition 5 holds.

Furthermore, condition 4 is satisfied:

{g(n), g(n − 1), g(n − 2), …, g(n − f(n))}
= {g(n), g(n − 1), g(n − 2), …, g(n − f(n − 1))}
= {g(n)} ∪ {g(n − 1), g(n − 2), …, g(n − f(n − 1))}
= {g(n − 1 − f(n − 1))} ∪ {g(n − 1), g(n − 2), …, g(n − f(n − 1))}
= {g(n − 1), g(n − 2), …, g(n − 1 − f(n − 1))}
= {0, 1, 2, … f(n − 1)}
= {0, 1, 2, … f(n)}

since f(n) = f(n − 1).

Readers who are mostly interested in Beatty’s Theorem can skip Theorem 2 since it can be omitted without loss of continuity. Now we expand the result of Theorem 1 as follows. First we need some notation. Let h be a function from the nonnegative integers N to the integers Z. Define the derived function h′ : N → Z as follows: h′(0) = 0 and for n ∈ N \ {0}, h′(n) = min(h′(n − 1) + 1, h(n)). Suppose h(0) = 0 and h satisfies the ujc, as required in the hypothesis of Theorem 1. Then it follows by mathematical induction that h = h′. Also note that h′ satisfies the ujc if and only if h′ is non-decreasing. The following illustrates a move function f such that the derived function f′ is non-decreasing. Note that (f′)′ = f′.

\begin{matrix}x & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ f(x) & 0 & 3 & 4 & 4 & 4 & 4 & 8 & 7 & 6 \\ f′(x) & 0 & 1 & 2 & 3 & 4 & 4 & 5 & 6 & 6 \end{matrix}

Theorem 2. The games (n, f) and (n, f′) have the same Nim values for any move function f : N → N such that f′ is non-decreasing.

Thus the class of functions for which we can solve the game is enlarged to all games (n, f) such that the derived function f′ satisfies the hypothesis of Theorem 1, a much larger class of games.

Proof. The proof is by induction. The base case: g((0, f)) = g((0, f′)) = 0 since these are both terminal positions. Now suppose g((k, f)) = g((k, f′)) for 0 ≤ k ≤ n − 1. To see that g((n, f)) = g((n, f′)), we consider the two cases a) f′(n) − f′(n − 1) = 0 and b) f′(n) − f′(n − 1) = 1. In case a) it follows from the definition of f′ that f′(n) = f(n). Then

g((n, f)) = mex({g(n − 1), g(n − 2), …, g(k − f(n))})
= mex({g(n − 1), g(n − 2), …, g(n − f′(n))}) = g((n, f′)).

On the other hand, in case b), from Theorem 1, g((n, f′)) = f′(n). Then g((n, f′)) = mex({g(n − 1), g(n − 2), …, g(n − f′(n))}) = f′(n). But applying condition 4 from Theorem 1 yields {g((n, f′)), g(n − 1), g(n − 2), …, g(n − f′(n))}) = {0, 1, 2, …, f′(n)}, so {g(n−1), g(n−2), …, g(n−f′(n))}) = {0, 1, 2, …, f′(n)−1} = {0, 1, 2, …, f′(n−1)}. Now g((n, f)) = mex({g(n − 1), g(n − 2), …, g(n − f(n))}). Since f(n) ≥ f′(n), this is equal to

mex({g(n−1), g(n−2), …, g(n−f′(n))}∪{g(n−1−f′(n)), g(n−2−f′(n)), …, g(n−f(n))})

= mex({0, 1, 2, …, f′(n − 1))} ∪ {g(n − 1 − f′(n)), g(n − 2 − f′(n)), …, g(n − f(n))})

But 0 ≤ g(n − i − f′(n)) ≤ f′(n − i − f′(n)) ≤ f′(n − 1) for i ∈ {1, 2, …, f(n) − f′(n)} by condition 5 of Theorem 1 and the fact that f′ is non-decreasing. Thus each g(n − i − f′(n)) lies in the set {0, 1, 2, …, f′(n − 1)} and therefore we have g(n, f) = mex({0, 1, 2, …, f′(n−1)}) = f′(n−1)+1 = f′(n), as was to be shown. Thus g((n, f)) = g((n, f′)) in either case, and this completes the inductive proof.

In order to use Theorem 1 more effectively with specific functions, we need Theorem 4, which generalizes Theorem 1. We also use the functions F (m), H(m) of Definition 3 when we generalize Beatty’s Theorem.

Definition 3. For any non-negative integer n, consider the game (n, f) where the move function f satisfies the four conditions

1. f(0) = 0 and

2. For all n ≥ 0, f(n + 1) − f(n) ∈ {0, 1}.

3. lim_{n→∞} f(n) = ∞.

4. lim_{n→∞} n − f(n) = ∞.

Let h(n) = n−f(n). Note that because of conditions 1-4, both h and f are surjections of N onto N. Thus for each integer m ≥ 0, we may define F (m) to be the smallest non-negative integer x such that f(x) = m, and H(m) to be the smallest non-negative integer x such that h(x) = m. Finally, let α be any non-negative integer and 0 ≤ a_{1} < a_{2} ⋯ < a_{i} < ⋯ be all the non-negative integers such that g(a_{i}) = α. That is, a_{1}, a_{2}, … is the sequence of pile sizes whose Nim values are α.

Theorem 4. The sequence a_{1}, a_{2}, … can be generated recursively as follows: a_{1} = F (α) and for all i = 2, 3, 4, …, a_{i} = H(a_{i−1} + 1).

The conditions 3 and 4 could be omitted, but the proof would be slightly more technical.

Proof. First note that

1. h(0) = 0,

2. for all n ≥ 0, h(n + 1) − h(n) ∈ {0, 1}, and

3. lim_{n→∞} h(n) = ∞.

We use Theorem 1 to prove Theorem 4 by induction on the index i in a_{1}, a_{2}, . . .. Since lim_{n→∞} f(n) = ∞ and lim_{n→∞} n − f(n) = lim_{n→∞} h(n) = ∞, we can use conclusion 2 once and conclusion 3 repeatedly to show that for all nonnegative integers α there are infinitely many nonnegative integers whose Nim value is α. Therefore it makes sense to talk about a_{1}, a_{2}, … as being the infinite increasing sequence of all non-negative integers whose Nim values are α. Since h and f satisfy the ujc, it follows that f(F (m)−1) = m−1 for all m ≥ 1 and h(H(m) − 1) = m − 1 for all m ≥ 1.

From condition 5 of Theorem 1, it follows that for all n ≥ 0, g(n) ≤ f(n). Therefore, from condition 2 of Theorem 1, a_{1} = F (α). Thus we may suppose for the induction hypothesis that 0 ≤ a_{1} = F (α) < a_{2} < a_{3} < … < a_{i} are all the non-negative integers up to and including a_{i} whose Nim values are α. We also suppose that these a_{i}’s are generated by a_{1} = F (α) and a_{k} = H(a_{k−1} + 1) for all k ∈ {2, 3, …, i}.

To complete the proof it remains to show that the next positive integer a_{i+1} whose Nim value is α is given by

a_{i+1} = H(a_{i} + 1).

To this end, let s be the smallest positive integer such that h(s) > a_{i}. Of course, s = H(a_{i} + 1). Also, a_{i} < s since h(n) ≤ n. Since h(n + 1) − h(n) ∈ {0, 1}, we have

i. s − f(s) = a_{i} + 1 and ii. (s − 1) − f(s − 1) = a_{i}.

We ignore this paragraph when a_{i} = s−1 because in this case the sets are empty. The condition h(n+1)−h(n) ∈ {0, 1} together with equation ii. above implies that for all t ∈ {a_{i} +1, a_{i} +2, …, s−1}, h(t) = t−f(t) ≤ a_{i}. Therefore, for t ∈ {a_{i} +1, a_{i} +2, …, s−1}, a_{i} ∈ {t − 1, t − 2, t − f(t)}. Therefore, g(a_{i}) = α ∈ {g(t − 1), g(t − 2), …, g(t − f(t))}, and for t in the above range, g(t) = mex{g(t − 1), g(t − 2), …, g(t − f(t))} ≠ α.

We now show that g(s) = α. This will complete the proof since s is the next integer after a_{i} such that g(s) = α and s = H(a_{i} + 1). Using equations i. and ii. above, we see that f(s) − f(s − 1) = 0. From conclusion 3 of Theorem 1 and equation i. above, we see that g(s) = g(s − f(s) − 1) = g(a_{i}) = α.

In order to apply Theorem 4, we will use the following material from the companion paper [4].

Definition 5. Suppose u, v are real functions on the domain [0, ∞). We say u and v are complementary if they satisfy

1. u(0) = v(0) = 0,

2. u and v are non-decreasing on [0, ∞), and

3. u(x) + v(x) = x for all nonnegative x.

It is easy to see that at least one of u and v is unbounded. As a technical convenience, we assume both are unbounded. It is easy to see that ∀ϵ > 0, ∀x ∈ [0, ∞), 0 ≤ u(x + ϵ) − u(x) ≤ ϵ and 0 ≤ v(x + ϵ) − v(x) ≤ ϵ. From this it follows that both u and v are continuous.

Lemma 6. Suppose u and v are complimentary functions. Define f : N → N, h : N → N by f(n) = ⌊u(n)⌋, h(n) = n−f(n) = n−⌊u(n)⌋ = ⌈n−u(n)⌉ = ⌈v(n)⌉. Since f and h satisfy the conditions of Definition 3, for every nonnegative integer m, F (m) and H(m) are defined by Definition 3. For any nonnegative integer m, define u^{−1}(m) to be the smallest nonnegative real number that satisfies u(u^{−1}(m)) = m and v^{−1}(m) to be the largest nonnegative real number satisfying v(v^{−1}(m)) = m. . Then F (m) = ⌈u^{−1}(m)⌉, and H(0) = 0, H(m + 1) = ⌊v^{−1}(m) + 1⌋.

Proof. We prove that ∀m ∈ {0, 1, 2, … }, (1) F (m) = ⌈u^{−1}(m)⌉. The proof that (2) H(0) = 0, H(m + 1) = ⌊v^{−1}(m) + 1⌋ is very similar and is left to the reader. An intuitive proof of (1) and (2) using pictures is also fairly easy. Formal proofs of these are also given in [4], where we assume that both u and v are strictly increasing. Considering m ∈ {0, 1, 2, … } to be fixed, we abbreviate u^{−1}(m) as u^{−1}. Thus u^{−1} is the smallest non-negative real number for which u(u^{−1}) = m. Also, define \overline{u} = ⌈u^{−1}⌉. Now it is easy to see that F (0) = ⌈u^{−1}(0)⌉ = 0. Therefore, we assume m ∈ {1, 2, 3, … }. Note that u^{−1}(m) = u^{−1} ≥ 1 since ∀x ∈ [0, ∞), 0 ≤ u(x) ≤ x. Since f satisfies the ujc, equality (1) is assured once we prove

a. f(\overline{u}) = ⌊u(\overline{u})⌋ = m, and

b. f(\overline{u} − 1) = ⌊u(\overline{u} − 1)⌋ = m − 1.

To prove a. note that \overline{u} − u^{−1} = \overline{ϵ}, where 0 ≤ \overline{ϵ} < 1. Then

⌊u(\overline{u})⌋ = ⌊u(u^{−1} + \overline{ϵ})⌋
= ⌊u(u^{−1} + \overline{ϵ}) − u(u^{−1}) + u(u^{−1})⌋
= ⌊u(u^{−1} + \overline{ϵ}) − u(u^{−1}) + m⌋
= m + ⌊u(u^{−1} + \overline{ϵ}) − u(u^{−1})⌋.

Also, 0 ≤ u(u^{−1} + \overline{ϵ}) − u(u^{−1}) ≤ \overline{ϵ} < 1. Therefore, ⌊u(u^{−1} + \overline{ϵ}) − u(u^{−1})⌋ = 0. Thus ⌊u(\overline{u})⌋ = m+⌊u(u^{−1} +\overline{ϵ})−u(u^{−1})⌋ = m. To prove (b), define \underline{u} = \overline{u}−1 = ⌈u^{−1} −1⌉. Let u^{−1} − \underline{u} = \underline{ϵ}, where 0 < \underline{ϵ} ≤ 1. Now ⌊u(\overline{u} − 1)⌋ = ⌊u(\underline{u})⌋ = ⌊u(u^{−1} − \underline{ϵ})⌋ = ⌊u(u^{−1} − \underline{ϵ}) − u(u^{−1})+u(u^{−1})⌋ = ⌊u(u^{−1}−\underline{ϵ})−u(u^{−1})⌋+m. Since u is non-decreasing and u^{−1} = u^{−1}(m) is the smallest non-negative real number satisfying u(u^{−1}) = m and 0 < \underline{ϵ}, it follows that 0 < u(u^{−1}) − u(u^{−1} − \underline{ϵ}) ≤ \underline{ϵ} ≤ 1. Therefore, −1 ≤ u(u^{−1} − \underline{ϵ}) − u(u^{−1}) < 0. Therefore, ⌊u(u^{−1} − \underline{ϵ}) − u(u^{−1})⌋ = −1. Thus ⌊u(\overline{u} − 1)⌋ = ⌊u(u^{−1} − \underline{ϵ}) − u(u^{−1})⌋ + m = m − 1.

The reader can easily see that the two sequences F (m), m = 1, 2, 3, …, and H(m + 1), m = 0, 1, 2, 3, … together partition the set of positive integers and also that the members of each of the two sequences are distinct. This result is a generalization of Beatty’s Theorem. In [4], we extend this in a natural way to achieve a more powerful version of this result in which the continuous, increasing functions u and v are completely independent.

5. Examples

Example 1 (Beatty’s Theorem) Define u(x) = \frac{x}{1+a} and v(x) = \frac{ax}{1+a}, a > 0. From lemma 6, F (m) = ⌈u^{−1}(m)⌉ = ⌈(1+a)m⌉ and H(m+1) = ⌊v^{−1}(m)+1⌋ = ⌊(1+1/a)m+ 1⌋. We know that F (m), m = 1, 2, …, and H(m+1), m = 0, 1, 2, …, together partition the set of positive integers and the members of each of the two sequences are distinct. Since H(0 + 1) = 1, it follows that F (m), m = 1, 2, … and H(m + 1), m = 1, 2, … partitions {2, 3, 4, … }. Now if a is irrational, then H(m + 1) = ⌈(1 + 1/a)m⌉. Therefore, if a is irrational, then the sequences ⌈(1 + a)m⌉, m = 1, 2, … and ⌈(1 + 1/a)m⌉, m = 1, 2, … partition {2, 3, … }, which is equivalent to Beatty’s Theorem.

The original solution to Beatty’s problem was provided by Ostrowski and Aitken [7] and generalized to a larger class of sequences by Lambek and Moser [6]. It appears that the Lambek and Moser approach is the inverse of our approach. Our approach arose from studying the Nim (ie, Sprague-Grundy) values of games, while it is quite possible that Lambek and Moser were not aware of connection with combinatorial games. In [3], Fraenkel used Beatty’s Theorem to study a generalized Wythoff’s game. He did not use Wythoff’s game to derive Beatty’s Theorem as we have done here with our game.

Example 2. Define u, v on [0, ∞) as follows:

u(x) = \{ \begin{matrix}x & if 0 ≤ x ≤ 1 \\ \sqrt{x} & if x > 1 \end{matrix}

and

v(x) = \{ \begin{matrix}0 & if 0 ≤ x ≤ 1 \\ x − \sqrt{x} & if x > 1 \end{matrix}

Define the move function f(n) = ⌊\sqrt{n}⌋, n = 0, 1, 2, . . .. Then h(n) = ⌈n − \sqrt{n}⌉, n = 0, 1, 2, . . .. We invite the reader to go through the technicalities of Lemma 6. Now u^{−1}(n) = n^{2}, n = 0, 1, 2, …, and v^{−1}(n) = \frac{2n+1+\sqrt{4n+1}}{2}, n = 0, 1, 2, …. Let a be any nonnegative integer and 0 ≤ a_{1} < a_{2} … be all of the nonnegative integers whose Nim values are a. Then a_{1}, a_{2}, … is generated recursively as follows: a_{1} = F (a) = ⌈u^{−1}(a)⌉ =

a^{2}, and for all i ∈ \{2, 3 …, \}, a_{i} = H(a_{i−1} + 1) = ⌊v^{−1}(a_{i−1}) + 1⌋ = ⌊^{\frac{2a_{i−1}+3+\sqrt{4a_{i−1}+1}}{2}}⌋ .

The reader will also note the following Beatty-like property. The sequences F (m) = m^{2}, m = 1, 2, 3, … and H(m + 1) = ⌊\frac{2m+3+\sqrt{4m+1}}{2}⌋ , m = 0, 1, 2, … are disjoint sequences of distinct positive integers whose union is the set of positive integers.

Example 3. Define u, v on [0, ∞) as follows:

u(x) = \{ \begin{matrix}0 & if 0 ≤ x ≤ 1 \\ 3x^{2/3} − 3x^{1/3} & if x > 1 \end{matrix}

and

v(x) = \{ \begin{matrix}x & if 0 ≤ x ≤ 1 \\ x − 3x^{2/3} + 3x^{1/3} & if x > 1 \end{matrix}

Define the move function f(n) = ⌊3n^{2/3} − 3n^{1/3}⌋, n = 0, 1, 2, . . .. Then h(n) = ⌈n − 3n^{2/3} + 3n^{1/3}⌉, n = 0, 1, 2, . . .. Now u^{−1}(0) = 0,

u^{−1}(n) = (\frac{1}{2} + \frac{1}{2}\sqrt{1 + 4n/3})^{3} , n = 1, 2, 3, …,

and

v^{−1}(n) = (1 + \sqrt[3]{n − 1})^{3} , n = 0, 1, 2, ….

Let a be any nonnegative integer and 0 ≤ a_{1} < a_{2} < … be all the nonnegative integers whose Nim values are a. Then a_{1}, a_{2}, … is generated recursively as follows: a_{1} = F (a) = ⌈u^{−1}(a)⌉ and for all i ≥ 2, a_{i} = H(a_{i−1} + 1) = ⌊v^{−1}(a_{i−1}) + 1⌋.

The reader will also note the following Beatty-like property:

F (m) = ⌈(\frac{1}{2} + \frac{1}{2}\sqrt{1 + 4m/3})^{3}⌉ , m = 1, 2, 3, …

and

H(m + 1) = ⌊(1 + \sqrt[3]{m − 1})^{3} + 1⌋ , m = 0, 1, 2, …

are disjoint sets of distinct positive integers whose union is the set of positive integers. Of course we chose u and v so that u^{−1} and v^{−1} could be represented in explicit form. When one or both u^{−1} and v^{−1} cannot be computed in explicit form, we leave it in implicit form the same way that sin^{−1}x is left in implicit form. The reader might also like to consider the following variations of the above example: f(n) = ⌈\sqrt{n}⌉, f(n) = ⌈n − \sqrt{n}⌉, f(n) = ⌊n−\sqrt{n}⌋, f(n) = ⌈rn⌉, 0 < r < 1, f(n) = ⌊rn⌋, 0 < r < 1, f(n) = ⌈3n^{2/3}−3n^{1/3}⌉. The cases where r = k/(k + 1) are especially interesting because they can be solved explicitly. Of course, the Beatty-like property will immediately follow as well.

6. Misère and Blocking Games

It is easy to see that all the games studied so far are special games as defined in section 3. Therefore, the misère versions of the composite games are solved by the strategy given in section 3.

Games with Blocking. Consider the game (n, f) that satisfies the hypothesis of Theorem 1. Let k denote a non-negative integer. On each move including the first, before the moving player moves, the opposing player can block up to k of the moving players options. We denote this game by (n, f, k). The nim values of (n, f, k) can be computed by the formula

g(n, f, k) = ⌊\frac{g(n, f)}{k + 1}⌋ .

References

[1] Sam Beatty, Problem 3173, American Mathematical Monthly, vol. 33, 1926, p.159.

[2] Flammenkamp, Achim, A. Holshouser, and H. Reiter, Dynamic One-Pile Blocking Nim, Electronic Journal of Combinatorics, Volume 10(1), 2003.

[3] Fraenkel, A. S. How to beat your Wythoff games’ opponents on three fronts, American Mathematical Monthly, vol. 89, 1982, pp. 353-361.

[4] Holshouser, A. and H. Reiter, An Extention of Beatty’s Theorem, Southwest Journal of Pure and Applied Mathematics, Issue 2, December, 2001 pp.24-29.

[5] Holshouser, A., H. Reiter, and J. Rudzinski, Dynamic One-Pile Nim, Fibonacci Quarterly, vol 41.3, June-July, 2003, pp 253-262.

[6] Lambek, J. and L. Moser, ”Inverse and Complementary Sequences of Natural Numbers”, American Mathematical Monthly, vol. 61, 1954, p.454. MR 16,17a.

[7] Ostrowski and Aitken, Solution to Problem 3173, American Mathematical Monthly, vol. 34, p. 159.