INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #G04

ON THE PERIODICITY OF GENUS SEQUENCES OF QUATERNARY GAMES

M. R. Allen

Department of Mathematics and Statistics, Dalhousie University, Halifax, Nova Scotia, Canada

                          ameghan@mathstat.dal.ca

Received: 10/5/06, Revised: 2/19/07, Accepted: 3/2/07, Published: 3/13/07

Abstract

The periodicity of the genus sequences of the heaps of finite quaternary games are examined. While the truncated genus sequence of the heaps of finite quaternary games becomes periodic, this is not true for the genus sequence in general. This contrasts with the known result that the genus sequence of the heaps of all finite subtraction games, a subset of finite quaternary games, becomes periodic.

1. Introduction

This paper assumes that the reader is familiar with the basics of combinatorial games, as presented in [5] and [7]; in particular, impartial games, outcome classes, and disjunctive sums.

How does a player win a combinatorial game? A player wins when she has played a winning move. In combinatorial games, it is often assumed that the winning move is to leave the other player with no moves available. However, this need not be the case. Combinatorial games can be played under two disjoint conventions, normal and misère, which differ in the choice of winning move.

Definition 1 A game is played under the normal play convention if the last player to move wins. A game is played under the misère play convention if the last player to move loses.

Almost all combinatorial game research has been in games played under the normal play convention due to an important result which is lacking for misère play: the Sprague-Grundy Theory for impartial normal play games ([9], [12]), which says that every impartial game played under the normal play convention is equivalent to a Nim heap. Unfortunately, there are misère games which do not behave like misère Nim, so no comparable theorem is possible.

Notation 1 We will denote a Nim heap with n tokens by n. We let ⊕ denote the binary operation of Nim sum.

For those unfamiliar with misère play, it may seem that a simple reversal of outcome classes is enough to form a complete theory of impartial misère games, however this is not true. The reader can check that the game 2 + 2 is a previous player win regardless of play convention.

Every impartial misère game has a sequence of numbers associated to it, called the Genus. Genus is the tool traditionally used for impartial misère play analysis (for example, see [2], [3], [6], or [8]). Recently, a newer method has been developed by Plambeck and Siegel to analyse impartial misère games: the misère quotient ([10], [11]). While the misère quotient is an exciting new development in the theory, there are still questions regarding impartial misère games relevant to genus.

1.1 Quaternary Games

Much of the work done on impartial misère games has concerned itself with games in which players remove tokens from heaps based on certain rules ([2], [3], [10]). We continue with this tradition by investigating quaternary games:

Definition 2 An quaternary game is an octal game 0.d_{1}d_{2} ⋯, where d_{i} ∈ {0, 1, 2, 3} for each i ∈ N.

We are often only concerned with quaternary games in which there is a limit to the number of tokens we can remove from a heap. This corresponds to a quaternary game 0.d_{1}d_{2}d_{3} ⋯ such that there exists a smallest N ∈ N such that for all n > N, d_{n} = 0. Quaternary games with this property are called finite with length N.

Definition 3 A subtraction game is a quaternary game such that for all d_{i}, d_{i} = 0 or 3.

Under the misère play convention, there are major differences between non-subtraction quaternary games and subtraction games. Every subtraction game behaves like misère Nim ([6], p.442), but not every quaternary game does (see [4], Appendix A). Moreover, we will show that finite subtraction games played under the misère play convention exhibit a periodicity result which finite quaternary games do not exhibit in general. The periodicity result becomes evident with the use of Genus. We quickly reproduce here the definitions and basic facts regarding genus. Full proofs of all results can be found in [4].

1.2 Genus

• The genus of an impartial game G, denoted by Γ (G), is a sequence of numbers written as g^{g_{0}g_{1}g_{2}g_{3}···} where

g = G^{+}(G), g_{0} = G^{−}(G), and for n ∈ N, g_{n} = G^{−} (G + ∑_{i=1}^{n} 2)

where

G^{+}(G) = \{ \begin{matrix}0 & if G has no options \\ mex\{G^{+}(G′) | G′ is an option of G\} & else, \end{matrix}

and

G^{−}(G) = \{ \begin{matrix}1 & if G has no options \\ mex\{G^{−}(G′) | G′ is an option of G\} & else. \end{matrix}

Those familiar with impartial games will notice that G^{+}(G) is the Nim heap to which G is equivalent.

• ([6], p.430) Suppose G is an impartial game with options G_{a}, G_{b}, G_{c},⋯ such that

Γ (G_{a}) = a^{a_{0}a_{1}a_{2}a_{3}···}, Γ (G_{b}) = b^{b_{0}b_{1}b_{2}b_{3}···}, Γ (G_{c}) = c^{c_{0}c_{1}c_{2}c_{3}···}, ⋯

Then Γ (G) = g^{g_{0}g_{1}g_{2}g_{3}···} is calculated as follows:

g = mex{a, b, c, ⋯ },
g_{0} = mex{a_{0}, b_{0}, c_{0}, ⋯ }, and
g_{n} = mex{g_{n−1}, g_{n−1} ⊕ 1, a_{n}, b_{n}, c_{n}, ⋯ } for n ∈ N.

• The M-truncated genus of an impartial game G, denoted by Γ_{M}(G), is the numbers in the genus up to and including g_{M}.

• For a game G, we say that the genus of G, g^{g_{0}g_{1}g_{2}g_{3}···}, stabilises if there exists an N ∈ Z^{≥0} such that for all n ≥ N,

g_{n+1} = g_{n} ⊕ 2.

• ([6], p.422) The genus of G always stabilises and we write Γ (G) = g^{g_{0}g_{1}g_{2}g_{3}···} as g^{g_{0}g_{1}···g_{N} (g_{N} ⊕2)} where N is the smallest non-negative integer such that for all u ≥ N, g_{u+1} = g_{u} ⊕ 2.

• ([6], p. 422) Given a Nim heap m,

Γ (m) = \{ \begin{matrix}0^{120} & if m = 0 \\ 1^{031} & if m = 1 \\ m^{m(m⊕2)} & else. \end{matrix}

• ([7], p. 137) Suppose G is a disjunctive sum of Nim heaps. Then Γ (G) = 0^{120}, 1^{031} or n^{n(n⊕2)} for n ∈ Z^{≥0}.

• Given an impartial misère game G, G is tame if Γ (G) = 0^{120}, 1^{031} or n^{n(n⊕2)} for n ∈ Z^{≥0} and every option of G is also tame. An impartial misère game is wild if it is not tame. Unfortunately, the definition of tame is far from standardised; [6], [7], and [11] all use varying definitions. The definition of tame used in this paper corresponds to that appearing in [7]. If a game is tame, we say that under the misère play convention, this game behaves like misère Nim. Otherwise, if it is wild, the game does not behave like misère Nim.

For heap based games, such as quaternary games, it is often beneficial to think of the genera of the heaps as entries in a table, which we call the Γ table.

Γ (h_{0}) = e e_{0} e_{1} e_{2} e_{3} e_{4} ⋯
Γ (h_{1}) = a a_{0} a_{1} a_{2} a_{3} a_{4} ⋯
Γ (h_{2}) = b b_{0} b_{1} b_{2} b_{3} b_{4} · · · .
⋮

Restricting ourselves to the first M + 2 columns gives us Γ_{M}. This is called the Γ_{M} table.

Γ_{M}(h_{0}) = e e_{0} e_{1} e_{2} ⋯ e_{M−1} e_{M}
Γ_{M}(h_{1}) = a a_{0} a_{1} a_{2} ⋯ a_{M−1} a_{M}
Γ_{M}(h_{2}) = b b_{0} b_{1} b_{2} ⋯ b_{M−1} b_{M} .
⋮

Definition 4 For a heap based game, the genus sequence of the heaps is the sequence of genus values Γ (h_{0}), Γ (h_{1}), Γ (h_{2}), · · ·. Similarly, the M-truncated genus sequence of the heaps is the sequence of M-truncated genus values Γ_{M}(h_{0}), Γ_{M}(h_{1}), Γ_{M}(h_{2}), · · ·.

There are two possibilities for a periodicity results - along the rows and along the columns. Since the genus always stabilises, every row eventually becomes periodic.

Definition 5 For a heap based game, we say that the genus sequence of the heaps is periodic if there exist N, p ∈ N such that for all n ≥ N, Γ (h_{n}) = Γ (h_{n+p}). Similarly, we say the that M-truncated genus sequence of the heaps is periodic if there exist T, u ∈ N such that for all t ≥ T, Γ_{M}(h_{t}) = Γ_{M}(h_{t+u}).

This paper is concerned with the behaviour of the columns of the Γ table as well as the non periodicity/periodicity of the genus sequence of the heaps of arbitrary quaternary games.

2. The Genera of Quaternary Games

We now have all the tools necessary to begin our examination of quaternary games. We start by examining subtraction games.

Theorem 6 For any finite subtraction game, the genus sequence of the heaps is periodic.

Proof. Let S be a subtraction game and h_{n} a heap of size n. Then h_{n} is tame and Γ (h_{n}) = 0^{120}, 1^{031}, or n^{n(n⊕2)} for n ∈ Z^{≥2} ([6], p. 442). Thus Γ (h_{n}) depends only on G^{+}(h_{n}). we know that the G^{+} sequence of a finite subtraction game becomes periodic ([1], p.148). Thus the genus sequence of the heaps of a finite subtraction game is periodic. □

Even though all subtraction games are tame and have periodic genus sequence, neither of these results is true for general quaternary games. Wild quaternary games are fairly common. For example, while there are no wild quaternary games of length two or less, there is one wild quaternary game of length three, twenty-one wild quaternary games of length four, 154 wild quaternary games of length five, and 739 wild quaternary games of length six. Appendix A of [4] lists all wild finite quaternary games of length six or less.

2.1 Periodicity

We begin with the following periodicity result.

Proposition 7 Given a finite quaternary game, there exists N, p ∈ N such that for all n ≥ N, G^{+}(h_{n}) = G^{+}(h_{n+p}). Similarly, for each v ∈ Z^{≥0}, there exists N_{v}, p_{v} ∈ N such that for all m ≥ N_{v}, G^{−} (h_{m} + ∑_{i=1}^{v} 2) = G^{−} (h_{m+p_{v}} + ∑_{i=1}^{v} 2). In other words, the values in each column in the Γ table of a finite quaternary game becomes periodic.

Proof. Consider the finite subtraction octal game 0.d_{1}d_{2} ⋯ d_{k} and n ≥ k +1. From h_{n}, there are at most k legal moves.

We begin by examining the first column in the Γ table. That is, the G^{+}(h_{n}) values. Suppose n ≥ k + 1. Then G^{+}(h_{n}) = mex{G^{+}(h_{n−i}) | d_{i} = 2 or 3}. Thus, G^{+}(h_{n}) ≤ k, since |{G^{+}(h_{n−i}) | d_{i} = 2 or 3}| ≤ k + 1, as there are at most k legal moves from any given heap, That is, G^{+}(h_{n}) = u for u ∈ {0, 1, ⋯, k}.

Let m = max{i | d_{i} = 2 or 3}. That is, m is the largest number of tokens which can be taken from a heap of size n. The sequence of G^{+} values from G^{+}(h_{n}) onwards depends only on the previous m values, G^{+}(h_{n−m}), G^{+}(h_{n−m+1}), …, G^{+}(h_{n−1}). Not all of these values will be in the mex set which determines G^{+}(h_{n}); the number m is an overestimation assuming that for all i ≤ m, d_{i} = 3.

Consider the subsequences of length m of the G^{+} values. Eventually there will be a subsequence which repeats itself since there are only a finite number of permutations of length m with k + 1 elements. That is, there exists p, l ∈ Z^{≥0} such that G^{+}(h_{n}) = G^{+}(h_{n+p}) for all n such that l ≤ n ≤ l + m.

We claim that G^{+}(h_{n+p}) = G^{+}(h_{n}) for all n ≥ l. To prove this, we proceed by induction on n. We have the base case from the preceding paragraph. Fix t ∈ Z^{≥0} and suppose that for all u < t, G^{+}(h_{(n+u)+p}) = G^{+}(h_{n+u}).

Consider

G^{+}(h_{n+t+p}) = mex{G^{+}(h_{(n+t+p)−i}) | d_{i} = 2 or 3}
= mex{G^{+}(h_{(n+t−i)+p}) | d_{i} = 2 or 3}
= mex{G^{+}(h_{n+t−i}) | d_{i} = 2 or 3} by inductive assumption
= mex{G^{+}(h_{(n+t)−i}) | d_{i} = 2 or 3}
= G^{+}(h_{n+t}).

which completes the induction. Therefore the first column of the Γ table becomes periodic.

The argument used to show that the G^{−}(h_{n}) and G^{−}(h_{n} + ∑_{i=1}^{v} 2) sequences become periodic is virtually identical to that of G^{+}(h_{n}). □

Examining truncated genera, we obtain the following periodicity result.

Theorem 8 Let G be a finite quaternary game with heaps denoted by h_{n}. Then the Mtruncated genus sequence of the heaps is periodic.

Proof. Consider the Γ_{M} table:

Γ_{M}(h_{0}) = 0 1 2 0 ⋯ 2  0
Γ_{M}(h_{1}) = a a_{0} a_{1} a_{2} ⋯ a_{M−1} a_{M}
Γ_{M}(h_{2}) = b b_{0} b_{1} b_{2} ⋯ b_{M−1} b_{M} .
⋮

By Proposition 7, each column becomes periodic. Let μ_{i} denote the pre-period length of column i. Let ρ_{i} denote the period length of column i. Then, for all n > max_{i=1}^{M}{μ_{i}}, Γ_{M}(h_{n}) = Γ_{M}(h_{n+p}) for p = ∏_{i=0}^{M} ρ_{i}. □

Corollary 9 If there exists M ∈ N such that for all h_{n}, m ≥ M,

G^{−} (h_{n} + ∑_{i=1}^{m} 2) = G^{−} (h_{n} + ∑_{i=1}^{m+2} 2) ,

then the genus sequence of the heaps is periodic.

Proof. The given requirement means that, thinking of the genera of the heaps as columns of a table, the M^{th} column equals the (M + 2n)^{th} column, and the (M + 1)^{th} column equals the (M +2n+1)^{th} column, for n ∈ N. That is, each Γ (h_{n}) has stabilised by the (M +1)^{th} column, so Γ_{M+1}(h_{n}) completely encodes all the information given in Γ (h_{n}), and so for N, p ∈ N such that Γ_{M+1}(h_{n}) = Γ_{M+1}(h_{n+p}) for all n ≥ N, we also obtain Γ (h_{n}) = Γ (h_{n+p}) for n ≥ N. □

Once we no longer truncate the genera of the heaps, we are no longer guaranteed periodicity, as will be shown with 0.122 213.

2.2 The Quaternary Game 0.122 213: A Counterexample

The counterexample presented for the claim that the genus sequence of the heaps is periodic for every finite quaternary game is the game 0.122 213.

We begin with some notation.

Notation 2 Let {a_{1}a_{2} ⋯ a_{n}}^{m} denote the string a_{1}a_{2} ⋯ a_{n} repeated m times. For example, {a_{1}a_{2}a_{3}}^{6} = a_{1}a_{2}a_{3} a_{1}a_{2}a_{3} a_{1}a_{2}a_{3} a_{1}a_{2}a_{3} a_{1}a_{2}a_{3} a_{1}a_{2}a_{3}.

Proposition 10 Let G = 0.122 213. For n ∈ Z^{≥0}, let h_{n} denote a heap of size n. Then

heap  genus  heap  genus
h_{24+40n} 2^{{{43131}^{2}{42020}^{2}}^{n}43131 431}  h_{44+40n} 3^{{{43131}^{2}{42020}^{2}}^{n}{43131}^{2}42020 420}
h_{25+40n} 2^{131{43131{42020}^{2}43131}^{n}431}  h_{45+40n} 1^{13143 131{{42020}^{2}{43131}^{2}}^{n}42020 420}
h_{26+40n} 0^{0{43131{42020}^{2}43131}^{n}43131 420}  h_{46+40n} 1^{04313 1{{42020}^{2}{43131}^{2}}^{n}{42020}^{2}431}
h_{27+40n} 0^{3131{{42020}^{2}{43131}^{2}}^{n}420}  h_{47+40n} 4^{3131{{42020}^{2}{43131}^{2}}^{n}{42020}^{2}431}
h_{28+40n} 3^{31{{42020}^{2}{43131}^{2}}^{n}420}  h_{48+40n} 2^{31{{42020}^{2}{43131}^{2}}^{n}{42020}^{2}43131 431}
h_{29+40n} 1^{{{42020}^{2}{43131}^{2}}^{n}42020 420}  h_{49+40n} 2^{{{42020}^{2}{43131}^{2}}^{n}{42020}^{2}43131 431}
h_{30+40n} 1^{120{42020{43131}^{2}42020}^{n}42020 431}  h_{50+40n} 0^{12042 020{{43131}^{2}{42020}^{2}}^{n}{43131}^{2}420}
h_{31+40n} 4^{0{42020{43131}^{2}42020}^{n}42020 431}  h_{51+40n} 0^{04202 0{{43131}^{2}{42020}^{2}}^{n}{43131}^{2}420}
h_{32+40n} 2^{2020{{43131}^{2}{42020}^{2}}^{n}43131 431}  h_{52+40n} 3^{2020{{43131}^{2}{42020}^{2}}^{n}{43131}^{2}42020 420}
h_{33+40n} 2^{20{{43131}^{2}{42020}^{2}}^{n}43131 431}  h_{53+40n} 1^{20{{43131}^{2}{42020}^{2}}^{n}{43131}^{2}42020 420}
h_{34+40n} 0^{{{43131}^{2}{42020}^{2}}^{n}{43131}^{2}420}  h_{54+40n} 1^{{{43131}^{2}{42020}^{2}}^{n+1}431}
h_{35+40n} 0^{13143 131{{42020}^{2}{43131}^{2}}^{n}420}  h_{55+40n} 4^{131{{43131}^{2}{42020}^{2}}^{n}{42020}^{2}431}
h_{36+40n} 3^{04313 1{{42020}^{2}{43131}^{2}}^{n}42020 420} h_{56+40n} 2^{0{43131{42020}^{2}43131}^{n+1}431}
h_{37+40n} 1^{3131{{42020}^{2}{43131}^{2}}^{n}42020 420}  h_{57+40n} 2^{3131{{42020}^{2}{43131}^{2}}^{n}{42020}^{2}43131 431}
h_{38+40n} 1^{31{{42020}^{2}{43131}^{2}}^{n}{42020}^{2}431}  h_{58+40n} 0^{31{{42020}^{2}{43131}^{2}}^{n+1}420}
h_{39+40n} 4^{{{42020}^{2}{43131}^{2}}^{n}{42020}^{2}431}  h_{59+40n} 0^{{{42020}^{2}{43131}^{2}}^{n+1}420}
h_{40+40n} 2^{12042 020{{43131}^{2}{42020}^{2}}^{n}43131 431} h_{60+40n} 3^{120{42020{43131}^{2}42020}^{n+1}420}
h_{41+40n} 2^{04202 0{{43131}^{2}{42020}^{2}}^{n}43131 431} h_{61+40n} 1^{0{42020{43131}^{2}42020}^{n+1}420}
h_{42+40n} 0^{2020{{43131}^{2}{42020}^{2}}^{n}{43131}^{2}420} h_{62+40n} 1^{2020{{43131}^{2}{42020}^{2}}^{n+1}431}
h_{43+40n} 0^{20{{43131}{42020}}^{n}{43131}^{2}420}  h_{63+40n} 4^{20{{43131}^{2}{42020}^{2}}^{n+1}431}

Proof. We proceed by induction on n. For n = 0, calculations give us

heap  genus  heap  genus
h_{24} 2^{43131 431}  h_{44} 3^{43131 43131 42020 420}
h_{25} 2^{13143 1}  h_{45} 1^{13143 13142 02042 0}
h_{26} 0^{04313 1420}  h_{46} 1^{04313 14202 04202 0431}
h_{27} 0^{31314 20}  h_{47} 4^{31314 20204 20204 31}

continued on next page

Continued from previous page

heap genus heap genus
h_{28} 3^{31420 20420}  h_{48} 2^{31420 20420 20431 31431}
h_{29} 1^{42020 420}  h_{49} 2^{42020 42020 43131 431}
h_{30} 1^{12042 02043 1}  h_{50} 0^{12042 02043 13143 13142 0}
h_{31} 4^{04202 0431}  h_{51} 0^{04202 04313 14313 1420}
h_{32} 2^{20204 31314 31}  h_{52} 3^{20204 31314 31314 20204 20}
h_{33} 2^{20431 31431}  h_{53} 1^{20431 31431 31420 20420}
h_{34} 0^{43131 43131 420}  h_{54} 1^{43131 43131 42020 42020 431}
h_{35} 0^{13143 13142 0}  h_{55} 4^{13143 13142 02042 02043 1}
h_{36} 3^{04313 14202 0420}  h_{56} 2^{04313 14202 04202 04313 1431}
h_{37} 1^{31314 20204 20}  h_{57} 2^{31314 20204 20204 31314 31}
h_{38} 1^{31420 20420 20431}  h_{58} 0^{31420 20420 20431 31431 31420}
h_{39} 4^{42020 42020 431}  h_{59} 0^{42020 42020 43131 43131 420}
h_{40} 2^{12042 02043 13143 1}  h_{60} 3^{12042 02043 13143 13142 02042 0}
h_{41} 2^{04202 04313 1431}  h_{61} 1^{04202 04313 14313 14202 0420}
h_{42} 0^{20204 31314 31314 20} h_{62} 1^{20204 31314 31314 20204 20204 31}
h_{43} 0^{20431 31431 31420}  h_{63} 4^{20431 31431 31420 20420 20431}

which shows the base case.

Suppose that for all n < k, the genus of a heap of size h_{i+40n}, for i ∈ {24, 25, ⋯, 63}, equals the genus given in the chart in the statement of the theorem. Call this (IH1). Consider n = k. We will only show the result for h_{24+40k}, as the method of proof is similar for all 39 other cases.

The moves available from h_{24+40k} are

h_{24+40k} ⟶^{−2} h_{24+40k−2} = h_{62+40(k−1)}
⟶^{−3} h_{24+40k−3} = h_{61+40(k−1)}
⟶^{−4} h_{24+40k−4} = h_{60+40(k−1)}
⟶^{−6} h_{24+40k−6} = h_{58+40(k−1)},

where each of the options falls under the induction hypothesis (IH1). That is,

Γ (h_{61+40(k−1)}) = 1^{2020{{43131}^{2}{42020}^{2}}^{k}431},
Γ (h_{61+40(k−1)}) = 1^{0{42020{43131}^{2}42020}^{k}420},
Γ (h_{60+40(k−1)}) = 3^{120{42020{43131}^{2}42020}^{k}420},
Γ (h_{58+40(k−1)}) = 0^{31{{42020}^{2}{43131}^{2}}^{k}420}.

We want

Γ (h_{24+40k}) = 2^{{{43131}^{2}{42020}^{2}}^{k}43131 431}.  (1)

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #G04 9

We begin with G^{+}(h_{24+40k}) and G^{−}(h_{24+40k}):

G^{+}(h_{24+40k}) = mex{1, 1, 3, 0} = 2,
G^{−}(h_{24+40k}) = mex{2, 0, 1, 3} = 4.

Therefore the base and the first superscript equal the desired result.

Consider G^{−} (h_{24+40k} + ∑_{i=1}^{m} 2) for m ∈ N. We claim that this equals the (m + 1)^{th} digit in the superscript of the genus on the RHS of Equation (1). We proceed by induction on m. Suppose m = 1. Then

G^{−}(h_{24+40k} + 2) = mex{G^{−}(h_{24+40k}), G^{−}(h_{24+40k}) ⊕ 1, G^{−}(h_{62+40(k−1)} + 2),
G^{−}(h_{61+40(k−1)} + 2), G^{−}(h_{60+40(k−1)} + 2), G^{−}(h_{58+40(k−1)} + 2)}
= mex{4, 5, G^{−}(h_{24+40k}) ⊕ 1, G^{−}(h_{62+40(k−1)} + 2),
G^{−}(h_{61+40(k−1)} + 2), G^{−}(h_{60+40(k−1)} + 2), G^{−}(h_{58+40(k−1)} + 2)}
= mex{4, 5, 0, 4, 2, 1} by (IH1)
= 3.

Now suppose the result holds for all m < 10k + 6, i.e.,

Γ (h_{24+40k}) = 2^{{{43131}^{2}{42020}^{2}}^{n}43131 4 g_{10k+6} g_{10k+7} g_{10k+8}···}  (2)

with g_{10k+i} ∈ Z^{≥0}, i ∈ {6, 7, ⋯ }.

Examining g_{10k+6}, we have:

g_{10k+6} = G^{−} (h_{24+40k} + ∑_{i=1}^{10k+6} 2)
= mex {G^{−} (h_{24+40k} + ∑_{i=1}^{10k+5} 2) , G^{−} (h_{24+40k} + ∑_{i=1}^{10k+5} 2) ⊕ 1,

G^{−} (h_{62+40(k−1)} + ∑_{i=1}^{10k+6} 2) , G^{−} (h_{61+40(k−1)} + ∑_{i=1}^{10k+6} 2) ,

G^{−} (h_{60+40(k−1)} + ∑_{i=1}^{10k+6} 2) , G^{−} (h_{58+40(k−1)} + ∑_{i=1}^{10k+6} 2)}

= mex {4, 5, G^{−} (h_{62+40(k−1)} + ∑_{i=1}^{10k+6} 2) , G^{−} (h_{61+40(k−1)} + ∑_{i=1}^{10k+6} 2) ,

G^{−} (h_{60+40(k−1)} + ∑_{i=1}^{10k+6} 2) , G^{−} (h_{58+40(k−1)} + ∑_{i=1}^{10k+6} 2)}

by Equation (2)

= mex{4, 5, 1, 2, 2, 0} by (IH1)
= 3,

as required. Similarly, g_{10k+7} = 1 and g_{10k+8} = 3.

By (IH1), the genus of each of the options has stabilised by this index and the genus of h_{24+40k} has exhibited stabilising behaviour. Thus, h_{24+40k} = 2^{{{43131}^{2}{42020}^{2}}^{n}43131 431}. □

Theorem 11 Let G = 0.122 213. Then the genus sequence of the heaps is not periodic.

Proof. Consider heaps h_{24+40n} for n ∈ Z^{≥0}. By Proposition 10,

Γ (h_{24+40n}) = 2^{{{43131}^{2}{42020}^{2}}^{n}43131 431},

and for heaps of size twenty-four or greater, the only heaps whose genera have 2^{43} as their starting digits are heaps of the form h_{24+40k} for some k ∈ Z^{≥0}. Thus, if the genus sequence of the heaps is periodic, there exists N ∈ Z^{≥0}, such that for all n, m ≥ N, Γ (h_{24+40n}) = Γ (h_{24+40m}).

We claim that for n ∈ Z^{≥0}, there does not exist m ∈ Z^{≥0} with m ≠ n such that Γ (h_{24+40n}) = Γ (h_{24+40m}). Fix n, m ∈ Z^{≥0} with n ≠ m, and suppose, without loss of generality, that n < m. By Proposition 10,

G^{−} (h_{24+40m} + ∑_{i=1}^{10m+5} 2) = 4,

while

G^{−} (h_{24+40n} + ∑_{i=1}^{10m+5} 2) = 1.

Therefore the genera of h_{24+40m} and h_{24+40n} cannot be the same if n does not equal m as there exists digits genera of h_{24+40m} and h_{24+40n} which are not equal. Hence, the genus sequence of the heaps is not periodic for 0.122 213. □

We see now that there can be no comparable periodicity result to Theorem 6 for quaternary games in general.

3. Conclusion

We conclude with an open question regarding the periodicity of the genus sequence of the heaps for finite quaternary games: Is there a method of classification to determine which finite quaternary games have their genus sequence of the heaps periodic versus those which do not other than through manual calculations similar to those given in the proof of Proposition 10? Perhaps an analysis of quaternary games under the misère quotient ([10], [11]) will yield the answer.

Acknowledgments

The author would like to acknowledge Dr. Richard Nowakowski of Dalhousie University for his help and advice in the preparation of this paper. The author also extends a thanks to her referees for their helpful advice.

References

[1] Michael Albert, Richard Nowakowski, and David Wolfe. Lessons in Play: An Introduction to the Combinatorial Theory of Games. A.K. Peters Ltd., Natick, MA, 2007.

[2] D.T. Allemang. “Generalized genus sequences for misère octal games”. International Journal of Game Theory, (30):539–556, 2001.

[3] D. T. Allemang. “Machine Computation with finite Games”, MSc Thesis, (Trinity College Cambridge), 1984.

   http://www.plambeck.org/oldhtm/mathematics/games/misere/allemang.

[4] M.R. Allen. “Impartial Combinatorial Misère Games”, MSc Thesis, (Dalhousie University), 2006.

   http://www.reluctantm.com/thesis/meghan.pdf.

[5] E.R. Berlekamp, J.H. Conway, and R.K. Guy. Winning ways for your mathematical plays. Vol. 1. A.K. Peters Ltd., Natick, MA, second edition, 2001.

[6] E.R. Berlekamp, J.H. Conway, and R.K. Guy. Winning ways for your mathematical plays. Vol. 2. A.K. Peters Ltd., Natick, MA, second edition, 2003.

[7] J.H. Conway. On Numbers and Games. A. K. Peters Ltd., Natick, MA, second edition, 2001.

[8] T.S. Ferguson. “A Note on Dawson’s Chess”. Unpublished research note, available at

   http://www.math.ucla.edu/ tom/papers/unpublished/DawsonChess.pdf

[9] P.M. Grundy. “Mathematics and games”. Eureka, 2:6–8, 1939.

[10] T.E. Plambeck. “Taming the Wild in Impartial Combinatorial Games”. INTEGERS: Electronic Journal of Combinatorial Number Theory 5(1), 2005.

[11] T.E. Plambeck, A. Siegel. “Misere quotients for impartial games”. Preprint.

[12] R. P. Sprague. “Über mathematische Kampfspiele”. Toohoku Math J. 43:438-444, 1935-6.