\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf
An Aperiodic Subtraction Game of \\
\vskip .11in
Nim-Dimension Two
}
\vskip 1cm
\large
Urban Larsson\footnote{Supported by the Killam Trust.}\\
Department of Mathematics and Statistics\\
Dalhousie University\\
6316 Coburg Road\\
P.O. Box 15000\\
Halifax, NS B3H 4R2\\
Canada\\
\href{urban031@gmail.com}{\tt urban031@gmail.com}\\
\ \\
Nathan Fox\\
Department of Mathematics\\
Rutgers University\\
110 Frelinghuysen Road\\
Piscataway, NJ 08854\\
USA\\
\href{fox@math.rutgers.edu}{\tt fox@math.rutgers.edu}
\end{center}
\vskip .2 in
\newcommand{\N}{\mathbb{N}}
\renewcommand{\ge}{\geqslant}
\renewcommand{\le}{\leqslant}
\begin{abstract}
In a recent manuscript, Fox studied infinite subtraction games with a
finite (ternary) and aperiodic Sprague-Grundy function. Here we provide
an elementary example of a game with the given properties, namely the
game given by the subtraction set $\{F_{2n+1}-1\}$, where $F_i$ is the
$i$th Fibonacci number, and $n$ ranges over the positive
integers.
\end{abstract}
\section{Introduction}
In a recent preprint, Fox~\cite{F} studied infinite and aperiodic subtraction games~\cite[p.\ 84]{B} with a finite, ternary, Sprague-Grundy function. For an impartial game, the Sprague-Grundy value is computed recursively as the least nonnegative integer not in the set of values of the move options, and starting with the terminal position(s) which have Sprague-Grundy value zero~\cite{S, G}. In this note we provide an elementary example of a game with the given properties. In particular, this means our game has nim-dimension two\footnote{The number of power-of-two-components defines the group of nim-values generated by the games; this group is of order four so the dimension is two. In the classical definition~\cite{Sa}, this dimension would have been one.}.
Let $\phi=\frac{1+\sqrt{5}}{2}$ denote the golden ratio. Let $A(n)=\lfloor n\phi \rfloor$, $B(n)=\lfloor n\phi^2 \rfloor$, and $AB(n) = A(B(n)) = A(n)+B(n)=2\lfloor n\phi \rfloor + n$ for all nonnegative integers $n$; see also Kimberling's paper~\cite{K}.
Then, define sets $A=\{A(n)\}_{n\geqslant1}$, $B = \{B(n)\}_{n\geqslant 1}$, and $AB = \{AB(n)\}_{n\geqslant 1}$. Further, let $B_0\oplus 1 = \{B(n) +1 \}_{n\geqslant 0}$, and $AB\oplus 1=\{2\lfloor n\phi \rfloor + n+1 \}_{n\geqslant 1}$. (In general, we let $X_0=X\cup \{0\}$ if $X$ is a set of integers.) It is worth noting that if the sets defined here are thought of as sequences, they all appear in the OEIS~\cite{oeis}. $A$ appears as \seqnum{A000201}, $B$ as \seqnum{A001950}, $AB$ as \seqnum{A003623}, $B_0\oplus1$ as \seqnum{A026352}, and $AB\oplus 1$ as \seqnum{A089910}.
Throughout this paper, we will use $F_i$ to denote the $i$th Fibonacci number ($F_1=F_2=1$ and so on).
We will frequently use the following famous numeration system: each positive integer is expressed uniquely as a sum of distinct non-consecutive Fibonacci numbers of index at least two. Though this representation has been discovered independently many times~\cite{Le,Os,Zeck}, it is typically referred to as the \emph{Zeckendorf representation}.
It is well known that $x\in A$ if and only if the smallest Fibonacci term in the Zeckendorf representation of $x$ has an even index~\cite{S}. Let $z_i = z_i(x)$ denote the $i$th smallest index of a Fibonacci term in the Zeckendorf representation of the number $x$. Then, the set $A$ contains all the numbers with $z_1\ge 2$ even. Further, for all $n$, $B(n)$ is the \emph{left-shift} of $A(n)$; that is, the set $B$ contains all the numbers with $z_1\ge 3$ odd.
Another well-known Fibonacci-type representation of integers is the \emph{least-odd} representation (which Silber \cite{S} calls the second canonical representation), where the smallest index is odd $\ge 1$ and no two consecutive Fibonacci numbers are used. Let $\ell_i(x)$ denote the $i$th smallest index in the least-odd representation of $x$. Then $\ell_1$ is odd. By using this representation we find that $A(n)$ is the left-shift of $n$ for any positive integer $n$. That is, if $n=F_{\ell_j}+\cdots +F_{\ell_1}$, then $A(n)=F_{\ell_j+1}+\cdots +F_{\ell_1+1}$.
\section{Our construction}
In this section, we will construct our example of an aperiodic subtraction game. Let $S=\{F_{2n+1}-1\}=\{1,4,12,\ldots \}$, where $n$ ranges over the positive integers.
The two-player subtraction game $S$ is played as follows. The players alternate in moving. From a given position, a nonnegative integer, $p$, the current player moves to a new integer of the form $p-s\ge 0$, where $s\in S$. A player unable to move, because no number in $S$ satisfies the inequality, loses. Our main result states that the sequence of Sprague-Grundy values for this game is a ternary, aperiodic sequence. First, we need the following lemma.
\begin{lemma}\label{lem1}
The sets $B_0$, $B_0\oplus 1$, $AB\oplus 1$ partition the nonnegative integers.
\end{lemma}
\begin{proof}
By the work of Wythoff~\cite{W}, it suffices to prove that the sets $B\oplus 1$ and $AB\oplus 1$ partition the set $A$.
Claim: For numbers in $AB\oplus 1$, we get $z_2\ge 4$ even and $z_1 = 2$. (Hence $AB\oplus 1\subset A$.) The claim is proved by noting that the least-odd representation coincides with the Zeckendorf representation for numbers of the form $B(n)$. Hence $AB(n)$ is the left-shift of $B(n)$, which proves the claim, since $z_1(B(n))\ge 3$.
We must also show that $B_0\oplus 1\subset A$ contains all representatives with $z_1\geqslant 4$ even. This follows, since $B$ contains all representatives with $z_1 = 3$ odd (since $F_4 = F_3+1$, $F_6 = F_5+F_3+1$ and so on). Further, since $B$ contains all representatives with $z_1\geqslant 5$ odd, $B\oplus 1$ contains all representatives with $z_2\geqslant 5$ odd and $z_1 = 2$. Finally, this set also contains the representative with just $z_1=2$.
\end{proof}
Note that because the golden ratio is an irrational number, the sets in Lemma~\ref{lem1} are aperiodic when thought of as sequences (in fact they follow a beautiful fractal pattern \cite[Thm.\ 2.1.13, p.\ 51]{L} related to the Fibonacci morphism).
We can now prove our main theorem.
\begin{theorem}
The Sprague-Grundy value of the subtraction game $S$ is $g(p)=0$ if $p\in B_0, g(p)=1$ if $p\in B_0\oplus 1$ and $g(p)=2$ if $p\in AB\oplus 1$.
\end{theorem}
\begin{proof}
We begin by showing that, if $p\in B_0$, then no follower of $p$ is in $B_0$, which corresponds to showing that $g(p)=0$. This holds for $p=0$. Thus, it suffices to show that $x=x(i)=p-F_{2i+1}+1\in A$, for all $i>0$ such that $p\geqslant F_{2i+1}$, which is true if and only if the Zeckendorf representation's smallest term is even indexed, i.e. $z_1(x)$ is even. It holds trivially unless $p-F_{2i+1}$ has as the smallest term $F_3$ or $F_2$. In case the former, then we compute $F_3+F_2$ and get $F_4$. Unless $F_5$ is contained in the representation we are done. Continuing this argument gives the claim in the first case.
We show next that $z_1(p-F_{2i+1})>2$.
Observe that
\begin{align}\label{ge3odd}
z_1(p)\ge 3 \text{ is odd. }
\end{align}
If $z_1(p)>2i+1$, that is, if the smallest Zeckendorf term, say $F_{2j+1}$, in $p$ has index greater than $2i+1$, then
\begin{align}\label{fibdiff}
F_{2j+1}-F_{2i+1}=F_{2j}+\cdots + F_{2i+2}.
\end{align}
Hence, in this case, $z_1(x)\ge 3$, so $F_2$ is not the smallest term. The case $i=j$ is trivial. Hence $j*2$, by (\ref{ge3odd}).
Suppose next that $p\in B_0\oplus 1$. We need to show that there is a follower in $B_0$, but no follower in $B_0\oplus 1$. Let $b=p-1\in B_0$. Then $b+1-(F_{2i+1}-1)=b-F_{2i+1}+F_3\in B$ if $i=1$ (which solves the first part). Suppose now, that $p$ has a follower in $B_0\oplus 1$. Then $b+1-(F_{2i+1}-1)\in B_0\oplus 1$, that is $b-(F_{2i+1}-1)\in B_0$, which is contradictory by the first paragraph.
At last we prove that if $p\in AB\oplus 1$ then $p$ has both a follower in $B_0$ and in $B_0\oplus 1$, but no follower in $AB\oplus 1$. We begin with the latter. Note that $z_1(p)=2$.
We want to show that $p-F_{2i+1}+1 \not \in AB\oplus 1$, for all $i$. Thus, it suffices to show $\alpha = p-F_{2i+1}\not \in AB$. We may assume that there is a smallest $k$ such that $F_k\ge F_{2i+1}$, and where $F_k$ is a term in the Zeckendorf representation of $p$. Claim: If $k$ is odd, then $\alpha\in A\setminus AB$, and otherwise $\alpha \in B\cup (A\setminus AB)$. It suffices to prove this claim to prove this case. For the first part it is easy to see that $z_1(\alpha)=2$, since $z_1(p)=2$ and by (\ref{fibdiff}). If $k$ is even, then we study the greatest Zeckendorf term in $p$, smaller than $F_{2i+1}$, say $F_\ell$ with existence of $\ell\le 2i$ clear by definition of $p$. If $\ell =2i$, then $F_k+F_\ell-F_{2i+1}=y+2F_{2i}=y+F_{2i+1}+F_{2i-2}$, where $y$ has no terms smaller than $F_{2i+3}$. If $\ell =2i-1$, then similarly $F_k+F_\ell-F_{2i+1}=y+F_{2i}+F_{2i-1}=y+F_{2i+1}$, and if $\ell < 2i-1$ then $F_k + F_\ell - F_{2i+1} = y + F_{2i}+F_\ell$. In these latter two cases the Zeckendorf representation of $\alpha$ is already clear, and $z_1(\alpha)=2$ which gives $\alpha\in A\setminus AB$. In case $\ell=2i$, we may need to repeat the argument, in particular if $F_{2i-2}$ belongs to the Zeckendorf representation of $p$, and possibly further repetition of this form will terminate with a representation of the form $y+2F_2=y+F_3$ with Zeckendorf indexes in $y$ greater than 5. This is the unique case where $z_1(\alpha)$ is odd and hence $\alpha\in B$. Any other case will give $z_1(\alpha)=2$ which gives $\alpha\in A\setminus AB$.
Next, we find an $i$ such that $p-(F_{2i+1}-1)\in B_0\oplus 1$. Take $i=1$. We show that $p-F_{3}\in B_0$. Write $p=a+F_2$ and show that $a - F_2\in B_0$, where $z_1(a)=2k\ge 4$ is even, by the definition of the set $AB$ and by $a=p-1$. By the identity $F_{2k}-F_2=F_{2k-1}+\cdots +F_3$, the result follows.
It remains to find an $i$ such that $\alpha = p-(F_{2i+1}-1)\in B_0$. With $a=p-1$, and since $p+1=a+F_3$, we may define $z_1(a)=F_{2k+2}$, with $k\ge 1$. With the Zeckendorf representation $a=y+F_{2k+2}$, we must show that $\alpha = y+F_{2k+2}+F_3-F_{2i+1}\in B_0$, for some $i$. If $k>1$, then we let $i=k$; if $k=2$, then $\alpha = y+F_{6}+F_3-F_{5}=y+F_5$, so $z_1(\alpha)=5$ and otherwise $z_1(\alpha)=3$. If $k=1$, then $z_1(a+F_3)=2\ell+1>3$. In case $a+F_3=F_{2\ell+1}$, then we choose $i=\ell$, and so $\alpha=0\in B_0$. Otherwise there is a smallest Zeckendorf term in $y$, say $F_{m}>F_{5}>F_{2k+2}$. Hence $\alpha = y'+F_m+F_{5}-F_{2i+1}$. If $m$ is odd, we let $i=(m-1)/2$, which gives $z_1(\alpha)=5$. Suppose $m$ is even, then, if $m\ge 8$, we let $2i+1=m-1$, which gives either $z_1(\alpha)=5$ or, in case $m=8$, $z_1(\alpha)=7$ (since the smallest Zeckendorf term in $y'$ is greater than $m+1=9$).
\end{proof}
Note that this example is also studied in Fox's manuscript~\cite{F} but with a less elementary proof. The sequence of Sprague-Grundy values for the game $S$ appears as sequence \seqnum{A242082} in OEIS.
\section{Acknowledgements}
Thanks to Carlos Santos for an enlightening discussion on the matter of nim-dimension.
\begin{thebibliography}{99}
\bibitem{B} E. R. Berlekamp, J. H. Conway, R. K. Guy, \emph{Winning Ways for your Mathematical Plays}, Volume 1, Academic Press, 1982.
\bibitem{F} N. Fox, On aperiodic subtraction games with bounded nim sequence, preprint, 2014, \url{http://arxiv.org/abs/1407.2823}.
\bibitem{G} P. M. Grundy, Mathematics and games, \emph{Eureka} {\bf 2} (1939), 6--8.
\bibitem{K} C. Kimberling, Complementary equations and Wythoff sequences,
\emph{J. Integer Sequences} {\bf 11} (2008),
\href{https://cs.uwaterloo.ca/journals/JIS/VOL11/Kimberling/kimberling719a.html}{Article 08.3.3}.
\bibitem{Le} C. G. Lekkerkerker,
Voorstelling van natuurlijke getallen door een som van
getallen van {Fibonacci}, \emph{Simon Stevin} {\bf 29} (1952), 190--195.
\bibitem{L} M. Lothaire, \emph{Algebraic Combinatorics on Words},
Cambridge University Press, 2002.
\bibitem{Os} A. Ostrowski, Bemerkungen zur {Theorie} der {Diophantischen}
{Approximationen}, \emph{Abh. Math. Sem. Hamburg} {\bf 1} (1922), 77--98,
250--251.
\bibitem{Sa} C.\ Santos, \emph{Some Notes on Impartial Games and Nim Dimension}, PhD Thesis, University of Lisbon (2010).
\bibitem{S} R. Silber, A Fibonacci property of Wythoff pairs, \textit{The Fibonacci Quarterly} {\bf 14} (1976), 380--384.
\bibitem{oeis} N. J. A. Sloane, \emph{The On-line Encyclopedia of Integer Sequences}, \url{http://www.oeis.org}.
\bibitem{Sp} R.\ P.\ Sprague, \"Uber mathematische Kampfspiele, \emph{T\^ohoku Mathematical Journal} {\bf 41} (1935), 438--444. Electronically available at \\
\url{https://www.jstage.jst.go.jp/article/tmj1911/41/0/41_0_438/_pdf}.
\bibitem{W} W. A. Wythoff, A modification of the game of Nim, \emph{Nieuw Arch. Wisk.} {\bf 7} (1907) 199--202.
\bibitem{Zeck} E. Zeckendorf, Repr\'esentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas. \emph{Bull. Soc. R. Sci. Li\`ege} {\bf 41} (1972), 179--182.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 91A46; Secondary 11B39.
\noindent \emph{Keywords: }
subtraction game, Fibonacci number, Sprague-Grundy function.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A000201},
\seqnum{A001950},
\seqnum{A003623},
\seqnum{A026352},
\seqnum{A089910}, and
\seqnum{A242082}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received April 9 2015;
revised versions received July 14 2015; July 15 2015.
Published in {\it Journal of Integer Sequences}, July 16 2015.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}
*