\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 $j2$, 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}