\documentclass[12pt]{article} \textwidth= 6.25in \textheight= 9.0in \topmargin = -10pt \evensidemargin=10pt \oddsidemargin=10pt \headsep=25pt \parskip=10pt \font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9 \usepackage{amsthm,latexsym,amssymb} %\input epsf.tex \newtheorem{proposition}{Proposition} \newtheorem{lemma}{Lemma} \newtheorem{corollary}{Corollary} \newtheorem{theorem}{Theorem} \newtheorem{definition}{Definition} \newtheorem{example}{Example} \newenvironment{pf}{\medskip\noindent{\it Proof}.}{} \font\amsx=msam10 \font\amsy=msbm10 \font\sfa=cmss10 scaled\magstep1 \def\IZ{\mathbb{Z}} %\def\IZ{\hbox{\amsy\char'132}} \def\bqed{\quad\hbox{\amsx\char'004}} \def\mex{\mathop{\rm mex}\nolimits} \begin{document} \vspace*{-60pt} \centerline{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 4 (2004), \#G06} \vskip 30pt \begin{center} \uppercase{\bf New games related to old and new sequences} \vskip 20pt {\bf Aviezri S. Fraenkel\footnote{\tt http://www.wisdom.weizmann.ac.il/$\sim$fraenkel}}\\ {\smallit Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel}\\ {\tt fraenkel@wisdom.weizmann.ac.il}\\ \vskip 30pt \centerline{\smallit Received: 2/19/04, Revised: 11/4/04, Accepted: 11/7/04, Published: 11/9/04} \vskip 30pt \end{center} \centerline{\bf Abstract} \noindent We define an infinite class of 2-pile subtraction games, where the amount that can be subtracted from both piles simultaneously, is a function $f$ of the size of the piles. Wythoff's game is a special case. For each game, the 2nd player winning positions are a pair of complementary sequences, some of which are related to well-known sequences, but most are new. The main result is a theorem giving necessary and sufficient conditions on $f$ so that the sequences are 2nd player winning positions. Sample games are presented, strategy complexity questions are discussed, and possible further studies are indicated. \noindent {\bf Keywords}: 2-pile subtraction games, complexity of games, integer sequences \pagestyle{myheadings} \markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 4 (2004), \#G06\hfill} \thispagestyle{empty} \baselineskip=15pt \vskip 30pt \section*{\normalsize 1. Introduction} %{\it Dominican International Forwarding\/} is the finest international %transportation company, according to its web site (in Spanish) at %http://www.dif.com.do . (An optional Google rendition confirms once %again that mechanical translation is still in its infancy.) What's %the connection of DIF to games? % %While pondering this question, let's introduce our first game: % %${\mathbf G_1}$ {\bf from dif.com.do}\medskip We begin with an example. Given two piles of tokens $(x,y)$ of sizes $x$, $y$, with $0\le x\le y<\infty$, two players alternate removing tokens from the piles according to the following two rules. A player, at his turn, can choose precisely one of them, as he sees fit. \begin{itemize} \item[(a)]~Remove any positive number of tokens from a single pile, possibly the entire pile. \item[(b)]~Remove a positive number of tokens from each pile, say $k,\ell$, so that $|k-\ell|$ isn't too large with respect to the position $(x_1,y_1)$ moved to from $(x_0,y_0)$, namely, $|k-\ell|0}$. Whereas the winning strategy of Wythoff's game is associated with sequences related to algebraic integers of the form $(2-t+\sqrt{t^2+4})/2$ (this is the golden section when $t=1$), our games give rise to an infinity of sequences, some well-known, but mostly new ones. In \S2 we shall see that the pair of sequences of $P$-positions associated with ${\mathbf G_1}$ is related to a ``self-generating'' sequence of Hofstadter (see Sloane \cite{Slo1999}). In \S3 we indicate how the $P$-positions of ${\mathbf G_2}$ are related to another well-known sequence. The central result appears in \S4, where a general theorem is formulated and proved, that yields winning strategies for a large class of 2-pile subtraction games. Roughly speaking it states that for every 2-pile subtraction game, if its constraint function $f$ is ``positive'', ``monotone'' and ``semi-additive'', then it has $P$-positions $(A, B)$, where $a_n$ satisfies (3), and $b_n$ has an explicit form depending on $f$. In a complementary proposition we show that positivity, monotonicity and semi-additivity are also necessary, in the sense that if any one of them is dropped, then there are constraint functions and their associated games $G$, such that the positions claimed to be $P$-positions by the central result, are not $P$-positions for these $G$. Theorems~1 and 2 are then deduced as simple corollaries of the central result. In \S5 we give an assortment of sample games with their $P$-positions that can be produced from the central theorem. Questions of complexity and related issues are discussed in \S6. The epilogue in \S7 wraps up with some concluding remarks and indications for further study. \vskip 30pt \section*{\normalsize 2. The G\"{o}del, Escher, Bach Connection} On p.~73 of Hofstadter's famous book \cite{Hof1979} the reader is asked to characterize the following sequence: \begin{center} $B'_{n\ge 0}=\{1,\ 3,\ 7,\ 12,\ 18,\ 26,\ 35,\ 45,\ 56,\dots\}$. \end{center} Answer: the sequence $\{2,\ 4,\ 5,\ 6,\ 8,\ 9,\ 10,\ 11,\dots\}$ constitutes the set of differences of consecutive terms of $B'_{n\ge 0}$, as well as the complement with respect to $\IZ_{>0}$ of $B'_{n\ge 0}$. For our purposes it is convenient to preface 0 to the latter sequence, so we define \begin{center} $A'_{n\ge 0}=\{0,\ 2,\ 4,\ 5,\ 6,\ 8,\ 9,\ 10,\ 11,\dots\}$, \end{center} which is the complement with respect to $\IZ_{\ge 0}$ of $B'_{n\ge 0}$. Now $a'_{10}=\mex\{a'_i, b'_i : 0\le i<10\}=13$, so $b'_{10}=56+13=69$. We see that in general, for all $n\in\IZ_{\ge 0}$, \begin{eqnarray} a'_n=\mex\left\{\{a'_i : 0\le i0}$ and $k+1\not\in S_n$, then the integers in the interval $[0,k+1]$ are in $S'_n$ and $k+2\not\in S'_n$. It follows that $\mex S'_n=a_{n+1}+1$. Also, $b'_{n+1}=b'_n+a'_{n+1}=b_n+1+a_{n+1}+1=b_{n+1}+1$.\hfill $\Box$ \end{pf} Thus the $P$-positions of $G_1$ constitute an ``offset by 1'' of the Hofstadter sequence and its complement.%, that is, $b_{n+1}-b_n=a_{n+1}+1$. So %$a_n+1$ is the difference and $a_n$ the complement of $b_n$. \vskip 30pt \section*{\normalsize 3. Prouhet-Thue-Morse} It is not hard to see that the sequence $A_{n\ge 1}$ of ${\mathbf G_2}$ contains precisely all positive integers whose binary representation ends in an even number of zeros. %(Because of this, %${\mathbf G_2}$ originates from even.com: ``www.even.com is the %best place to find information and sources for even'', it says on %its webpage.) The sequence $A_{n\ge 1}$ is also lexicographically minimal with respect to the property that the parity of the number of 1's in the binary expansion alternates. Furthermore, it is lexicographically minimal with respect to the property that the complement is the double of the sequence. If $m$ appears in $A$, then $2m$ appears in $B$. In particular, $B_{n\ge 1}$ contains precisely all positive integers whose binary representation ends in an odd number of zeros \cite{CSH1972}. The sequence \begin{eqnarray*} C_n&=&0^{a_1-a_0}1^{a_2-a_1}0^{a_3-a_2}\dots 0^{a_{2n+1}-a_{2n}}1^{a_{2n+2}-a_{2n+1}}\dots \\ &=&011010011001011010010\dots, \end{eqnarray*} is the Prouhet-Thue-Morse sequence, which arises in many different areas of mathematics. See the charming paper \cite{AlSh1999}, which also contains the sequence $A$, for many further properties of these sequences. \vskip 30pt \section*{\normalsize 4. A Master Theorem} The three previously described games ${\mathbf G_1}$, ${\mathbf G_2}$, ${\mathbf G_3}$, are members of an infinite family of games that we now formulate. We will then provide a general winning strategy for this family of games and prove its validity. \noindent {\bf General 2-pile subtraction games} Given two piles of tokens $(x,y)$ of sizes $x$, $y$, with $0\le x\le y<\infty$. %whose $P$-positions are ${\cal P}=\cup_{i=0}^{\infty} (a_i,b_i)$. Two players alternate removing tokens from the piles: (aa)~Remove any positive number of tokens from a single pile, possibly the entire pile. (bb)~Remove a positive number of tokens from each pile, say $k,\ell$, so that $|k-\ell|$ isn't too large with respect to the position $(x_1,y_1)$ moved to from $(x_0,y_0)$, namely, $|k-\ell|0\ \ \forall y_1\ge x_1\ge 0\ \ \forall x_0>x_1.$$ %\end{eqnarray*} \item Monotonicity: %\begin{eqnarray*} $$x'_0m\ge 0$, %\begin{eqnarray*} $$\sum_{i=0}^m f(a_{n-1-i},b_{n-1-i},a_{n-i})\ge f(a_{n-m-1},b_{n-m-1},a_n).$$ %\end{eqnarray*} \end{itemize} The player making the move after which both piles are empty wins; the opponent loses. In view of (8), positivity is a natural condition. Without positivity, a move of type~(bb) isn't even possible. Monotonicity appears to be a minimal requirement to enforce positivity. Semi-additivity is a convenient condition to have, and many functions are semi-additive. %It turns out %that though semi-additivity is defined on the $P$-positions, checking %whether it holds or not doesn't normally require knowledge of the %$P$-positions themselves; their positivity alone suffices. Whereas positivity and monotonicity are defined on any game positions, semi-additivity is defined on the candidate $P$-positions. All three conditions are applied to $P$-positions. If all three are satisfied, then the candidates are indeed $P$-positions, as enunciated in Theorem~3 below. The function f depends on three independent variables $x_1, y_1, x_0$ or $a_{n-1}, b_{n-1}, a_n$, and the dependent variable $b_n$ --- so that $(a_n, b_n)\in {\cal P}$ --- is then computed by $f$. Note that ${\mathbf G_1}$, ${\mathbf G_2}$, ${\mathbf G_3}$ clearly satisfy positivity and monotonicity; ${\mathbf G_1}$ and ${\mathbf G_3}$, in whose functions $f$ there is no $a_n$, are clearly semi-additive; and ${\mathbf G_2}$ is semi-additive with equality. (See also the proof of Theorems~1 and 2 at the end of this section.) \begin{theorem} Let ${\cal S}=\cup_{i=0}^{\infty} (a_i,b_i)$, where, for all $n\in\IZ_{\ge 0}$, $a_n$ is given by {\rm (3)}, $b_0=0$, and for all $n\in\IZ_{>0}$, \begin{eqnarray} b_n=f(a_{n-1},b_{n-1},a_n)+b_{n-1}+a_n-a_{n-1}. \end{eqnarray} If $f$ is positive, monotone and semi-additive, then ${\cal S}$ is the set of $P$-positions of a general {\rm 2}-pile subtraction game with constraint function $f$, and the sequences $A$, $B$ share the following common features: $(i)$ they partition $\IZ_{\ge 1}$$;$ $(ii)$ $b_{n+1}-b_n\ge 2$ for all $n\in\IZ_{\ge 0}$$;$ $(iii)$ $a_{n+1}-a_n\in\{1,2\}$ for all $n\in\IZ_{\ge 0}$. \end{theorem} \begin{pf} The definition of $a_n$ implies directly, \begin{eqnarray} a_n>a_{n-1} \end{eqnarray} for all $n\in\IZ_{>0}$. >From (9) we have, for all $n\in\IZ_{>0}$, \begin{eqnarray} &&b_n-b_{n-1}=f(a_{n-1},b_{n-1},a_n)+a_n-a_{n-1}, \\ &&b_n-a_n=f(a_{n-1},b_{n-1},a_n)+b_{n-1}-a_{n-1}. \end{eqnarray} Now $f(a_0,b_0,a_1)>0$ by positivity, so $b_1-b_0\ge 2$ by (10), (11). Hence we get, by induction on $n$, \begin{eqnarray} b_n-b_m\ge 2 {\rm\ for\ all\ } n>m\ge 0. \end{eqnarray} Similarly we get from (12), \begin{eqnarray} b_n-a_n>b_m-a_m\ge 0 {\rm\ for\ all\ } n>m\ge 0. \end{eqnarray} %Let $A=\cup_{n=1}^{\infty} A_n$ and $B=\cup_{n=1}^{\infty} B_n$. Now $A$ and $B$ are {\it complementary\/} sets of integers, i.e., $A\cup B=\IZ_{\ge 1}$ (by (3)), and $A\cap B=\emptyset$. Indeed, if $a_n=b_m$, then $n>m$ implies that $a_n$ is the mex of a set containing $b_m=a_n$, a contradiction to the mex definition; and $1\le n\le m$ is impossible since \begin{eqnarray*} b_m&=&f(a_{m-1},b_{m-1},a_m)+b_{m-1}+a_m-a_{m-1} \\ &\ge&f(a_{m-1},b_{m-1},a_n)+b_{n-1}+a_n-a_{n-1} \\ &&{\rm\ \left(by\ (10),\ (14)\ and\ monotonicity\right)} \\ &>&a_n\ ({\rm by\ positivity}). \end{eqnarray*} Since $b_n-b_{n-1}\ge 2$ for all $n\ge 1$ by (13), and since $A$ and $B$ are complementary, \begin{eqnarray} a_n-a_{n-1}\in\{1,2\} \end{eqnarray} for all $n\in\IZ_{>0}$. %Denote by ${\cal P'}$ the set of all positions $(A_n,B_n)$ satisfying %(3) and (9), For the remainder of the proof it is useful to denote the set ${\cal S}$ defined in the statement of the theorem by ${\cal P'}$. Also let ${\cal N'}=\IZ_{\ge 0}\setminus {\cal P'}$. For showing that ${\cal P'}={\cal P}$ and ${\cal N'}={\cal N}$, it evidently suffices to show two things: \begin{itemize} \item[I.]~Every move from any $(a_n,b_n)\in{\cal P'}$ results in a position in the complement ${\cal N'}$. \item[II.]~From every position $(x,y)$ in the complement ${\cal N'}$, there is a move to some $(a_n,b_n)\in {\cal P'}$. \end{itemize} (It is useful to note that these two conditions are also necessary: (1) implies that {\it all\/} positions reachable in one move from a $P$-position are $N$-positions; whereas (2) shows that at least one $P$-position is reachable in one move from an $N$-position.) I.~A move of type~(aa) from $(a_n,b_n)\in{\cal P'}$ has the form $(x,b_n)$ or $(a_n,y)$ $\ (x0}$ appears exactly once in exactly one of $A$ and $B$. Therefore we have either $x=b_n$ or else $x=a_n$ for some $n\ge 0$. (i)~$x=b_n$. Then move $y\rightarrow a_n$. This is always possible since if $n=0$, then $y>a_0=b_0$; whereas $a_nb_n$, move $y\rightarrow b_n$. So suppose that $a_n\le yb_m$. By (16), $y-a_n\ge b_m-a_m$. Hence $y-b_m\ge a_n-a_m>0$. \item The move satisfies (bb): \begin{eqnarray*} |(y-b_m)-(x-a_m)|&=&|(y-a_n)-(b_m-a_m)| \\ &=&(y-a_n)-(b_m-a_m) \end{eqnarray*} where the last equality follows from (16) and our choice of $m$. We thus have $|(y-a_n)-(b_m-a_m)|=(y-a_n)-(b_m-a_m)0})$. \end{proposition} \begin{pf} Consider the function $f(x_1,y_1,x_0)=(x_0-x_1)^2$. It is clearly positive and monotone. However, $(a_n-a_{n-1})^2+(a_{n-1}-a_{n-2})^2 <(a_n-a_{n-2})^2$, no matter whether $a_n-a_{n-1}=a_{n-1}-a_{n-2}=1$ or otherwise, so $f$ is not semi-additive. From (9) we get, $b_n=b_{n-1}+(a_n-a_{n-1})(a_n-a_{n-1}+1)$, where $a_n$ satisfies (3). The first few values of $(a_n, b_n)$ are depicted in Table~4. Note that these are not $P$-positions: we can move $(a_n,b_n)\rightarrow (a_i,b_i)$ in many ways; e.g., $(4,10)\rightarrow (0,0)$ satisfies (bb). \begin{table} \begin{center} \setlength{\tabcolsep}{4.87pt} \centerline{\small Table 4. The first few values of ${\cal S}$ for $f=(x_0-x_1)^2$.} \begin{tabular}{|r|rrrrrrrrrrrrrrrrr|} \hline &&&&&&&&&&&&&&&&&\\ $n$ &0 &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 &11 &12 &13 & 14 &15 &16 \\ &&&&&&&&&&&&&&&&& \\ \hline &&&&&&&&&&&&&&&&& \\ $a_n$ &0 &1 &3 &4 &5 &6 &7 &9 &11 &13 &15 &17 &18 &19 &20 &21 &23 \\ &&&&&&&&&&&&&&&&& \\ $b_n$ &0 &2 &8 &10 &12 &14 &16 &22 &28 &34 &40 &46 &48 &50 &52 &54 &60 \\ &&&&&&&&&&&&&&&&& \\ \hline \end{tabular} \end{center} \end{table} The function $f(x_1,y_1,x_0)=\lfloor(x_1+1)/x_0\rfloor+1$ is positive. Since $$\left(\left\lfloor\frac{a_{n-1}+1}{a_n}\right\rfloor+1\right)+ \left(\left\lfloor\frac{a_{n-2}+1}{a_{n-1}}\right\rfloor+1\right)> \left\lfloor\frac{a_{n-2}+1}{a_n}\right\rfloor+1=1,$$ it is also semi-additive. But it is not monotone. From (9), $b_n=b_{n-1}-a_{n-1}+a_n+\lfloor(a_{n-1}+1)/a_n\rfloor+1$. The first few values of ${\cal S}=\cup_{n=0}^{\infty} (a_n, b_n)$ are shown in Table~5. The game-position $(4,7)\not\in{\cal S}$, but it cannot be moved into ${\cal S}$. Hence ${\cal S}\not ={\cal P}$. (Incidentally, note that the sequence $B$ consists of all nonnegative multiples of 3.) \begin{table} \begin{center} \setlength{\tabcolsep}{4.87pt} \centerline{\small Table 5. The first few values of ${\cal S}$ for $f=\lfloor(x_1+1)/x_0\rfloor+1$.} \begin{tabular}{|r|rrrrrrrrrrrrrrrrr|} \hline &&&&&&&&&&&&&&&&&\\ $n$ &0 &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 &11 &12 &13 & 14 &15 &16 \\ &&&&&&&&&&&&&&&&& \\ \hline &&&&&&&&&&&&&&&&& \\ $a_n$ &0 &1 &2 &4 &5 &7 &8 &10 &11 &13 &14 &16 &17 &19 &20 &22 &23 \\ &&&&&&&&&&&&&&&&& \\ $b_n$ &0 &3 &6 &9 &12 &15 &18 &21 &24 &27 &30 &33 &36 &39 &42 &45 &48 \\ &&&&&&&&&&&&&&&&& \\ \hline \end{tabular} \end{center} \end{table} Lastly, consider $f(x_1,y_1,x_0)=\left(1+(-1)^{y_1+1}\right)x_1/2$. We see easily that $f$ is semi-additive, and it's trivially monotone. But whenever $y_1$ is even, $f$ is not positive. We have, $b_n=a_n+b_{n-1}-\left(1+(-1)^{b_{n-1}}\right)a_{n-1}/2$. Table~6 shows the first few ${\cal S}$-positions. These are not $P$-positions: The position $(10,29)\not\in {\cal S}$, cannot be moved into any position in ${\cal S}$.\hfill $\Box$ \begin{table} \begin{center} \setlength{\tabcolsep}{5.05pt} \centerline{\small Table 6. The first few values of ${\cal S}$ for $f=\left(1+(-1)^{y_1+1}\right)x_1/2$.} \begin{tabular}{|r|rrrrrrrrrrrrrrrrr|} \hline &&&&&&&&&&&&&&&&&\\ $n$ &0 &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 &11 &12 &13 &14 &15 &16 \\ &&&&&&&&&&&&&&&&& \\ \hline &&&&&&&&&&&&&&&&& \\ $a_n$ &0 &1 &2 &4 &5 &6 &8 &9 &10 &11 &14 &15 &16 &17 &18 &19 &20 \\ &&&&&&&&&&&&&&&&& \\ $b_n$ &0 &1 &3 &7 &12 &13 &21 &30 &31 &42 &45 &60 &61 &78 &79 &98 &99 \\ &&&&&&&&&&&&&&&&& \\ \hline \end{tabular} \end{center} \end{table} \end{pf} \noindent {\it Proof of Theorems 1 and 2}. The function $f(x_1,y_1,x_0)=x_1+1$ is clearly positive. Monotonicity is satisfied trivially. It's also clear that $f$ is semi-additive. The function $f(x_1,y_1,x_0)=x_0-x_1$ is positive, since $x_0>x_1$. It's also monotone. Since $(a_{n+1}-a_n)+(a_n-a_{n-1})=a_{n+1}-a_{n-1}$, we see that $f$ is semi-additive. Finally, the function $f(x_1,y_1,x_0)=y_1-x_1+1$ is positive for all $x_1\le y_1$ and is trivially monotone. It's also semi-additive. Thus by Theorem~3 we have for ${\mathbf G_1}$, $b_n=a_{n-1}+1+b_{n-1}-a_{n-1}+a_n=b_{n-1}+a_n+1$, as stated in Theorem~1. For ${\mathbf G_2}$, (9) implies, $b_n=a_n-a_{n-1}+b_{n-1}-a_{n-1}+a_n =2a_n-2a_{n-1}+b_{n-1}=2a_n$, where the last equality follows by induction on $n$. For ${\mathbf G_3}$, $b_n=b_{n-1}-a_{n-1}+1+b_{n-1}-a_{n-1}+a_n= 2(b_{n-1}-a_{n-1})+a_n+1=a_n+2^n-1$. Again the last equality follows by induction.\hfill $\Box$ \vskip 30pt \section*{\normalsize 5. Further Sample Games} For the examples below, we leave it to the reader to verify positivity, monotonicity and semi-additivity of $f$. Some of these examples are elaborated on in the next two sections. \begin{example} {\rm $f(x_1,y_1,x_0)=x_1-\lfloor(x_1+1)/x_0\rfloor+2$. Then $b_n=b_{n-1}+a_n-\lfloor(a_{n-1}+1)/a_n\rfloor+2$. The first few $P$-positions are depicted in Table~7. \begin{table} \begin{center} \setlength{\tabcolsep}{4.2pt} \centerline{\small Table 7. The first few values of ${\cal S}$ for $f=x_1-\lfloor(x_1+1)/x_0\rfloor+2$.} \begin{tabular}{|r|rrrrrrrrrrrrrrrrr|} \hline &&&&&&&&&&&&&&&&&\\ $n$ &0 &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 &11 &12 &13 & 14 &15 &16 \\ &&&&&&&&&&&&&&&&& \\ \hline &&&&&&&&&&&&&&&&& \\ $a_n$ &0 &1 &3 &4 &5 &6 &8 &9 &10 &11 &13 &14 &15 &16 &17 &19 &20 \\ &&&&&&&&&&&&&&&&& \\ $b_n$ &0 &2 &7 &12 &18 &25 &35 &45 &56 &68 &83 &98 &114 &131 &149 &170 &191 \\ &&&&&&&&&&&&&&&&& \\ \hline \end{tabular} \end{center} \end{table}} \end{example} \begin{example} {\rm $f(x_1,y_1,x_0)=x_0-x_1+2$. Then $b_n=b_{n-1}+2(a_n-a_{n-1}+1)=2(a_n+n)$. See Table~8 for the first few $P$-positions. \begin{table} \begin{center} \setlength{\tabcolsep}{4.87pt} \centerline{\small Table 8. The first few values of ${\cal S}$ for $f=x_0-x_1+2$.} \begin{tabular}{|r|rrrrrrrrrrrrrrrrr|} \hline &&&&&&&&&&&&&&&&&\\ $n$ &0 &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 &11 &12 &13 & 14 &15 &16 \\ &&&&&&&&&&&&&&&&& \\ \hline &&&&&&&&&&&&&&&&& \\ $a_n$ &0 &1 &2 &3 &5 &6 &7 &9 &10 &11 &13 &14 &15 &16 &17 &19 &20 \\ &&&&&&&&&&&&&&&&& \\ $b_n$ &0 &4 &8 &12 &18 &22 &26 &32 &36 &40 &46 &50 &54 &58 &62 &68 &72 \\ &&&&&&&&&&&&&&&&& \\ \hline \end{tabular} \end{center} \end{table}} \end{example} \begin{example} {\rm $f(x_1,y_1,x_0)=(-1)^{y_1}-(-1)^{x_1}+3$. Then $b_n=b_{n-1}-a_{n-1}+a_n+(-1)^{b_{n-1}}-(-1)^{a_{n-1}}+3$. See Table~9 for the first few $P$-positions. \begin{table} \begin{center} \setlength{\tabcolsep}{4.75pt} \centerline{\small Table 9. The first few values of ${\cal S}$ for $f=(-1)^{y_1}-(-1)^{x_1}+3$.} \begin{tabular}{|r|rrrrrrrrrrrrrrrrr|} \hline &&&&&&&&&&&&&&&&&\\ $n$ &0 &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 &11 &12 &13 &14 &15 &16 \\ &&&&&&&&&&&&&&&&& \\ \hline &&&&&&&&&&&&&&&&& \\ $a_n$ &0 &1 &2 &3 &5 &6 &7 &8 &9 &11 &12 &13 &15 &16 &17 &18 &19 \\ &&&&&&&&&&&&&&&&& \\ $b_n$ &0 &4 &10 &14 &21 &25 &27 &31 &33 &38 &44 &48 &55 &59 &61 &65 &67 \\ &&&&&&&&&&&&&&&&& \\ \hline \end{tabular} \end{center} \end{table}} \end{example} \begin{example} {\rm $f(x_1,y_1,x_0)=x_1\left(1+(-1)^{x_1}\right)+1$. This leads to $b_n=b_{n-1}+(-1)^{a_{n-1}}a_{n-1}+a_n+1$. Table~10 exhibits the first few $P$-positions. \begin{table} \begin{center} \setlength{\tabcolsep}{4.35pt} \centerline{\small Table 10. The first few values of ${\cal S}$ for $f=x_1\left(1+(-1)^{x_1}\right)+1$.} \begin{tabular}{|r|rrrrrrrrrrrrrrrrr|} \hline &&&&&&&&&&&&&&&&&\\ $n$ &0 &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 &11 &12 &13 &14 &15 &16 \\ &&&&&&&&&&&&&&&&& \\ \hline &&&&&&&&&&&&&&&&& \\ $a_n$ &0 &1 &3 &4 &6 &8 &9 &10 &11 &12 &13 &14 &15 &16 &17 &19 &20 \\ &&&&&&&&&&&&&&&&& \\ $b_n$ &0 &2 &5 &7 &18 &33 &42 &44 &66 &68 &94 &96 &136 &138 &172 &175 &177 \\ &&&&&&&&&&&&&&&&& \\ \hline \end{tabular} \end{center} \end{table}} \end{example} \vskip 30pt \section*{\normalsize 6. Computational Complexity Issues} What is the computational complexity of computing the winning strategy for our games? Given a position $(x,y)$ with $0\le x\le y<\infty$, the {\it statement\/} of Theorem~3 enables us to compute the table of $P$-positions. It suffices to compute it up to the smallest $n=n_0$ such that $a_{n_0}\ge x$, and thus determine whether $(x,y)\in{\cal P}$ or in ${\cal N}$. The {\it proof\/} of Theorem~3 then enables us, if $(x,y)\in{\cal N}$, to make a winning move to a position in ${\cal P}$. The latter part of the strategy, that of making a winning move, is clearly polynomial. The first part, determining whether or not $(x,y)\in{\cal P}$ is linear in $x$, since $a_{n_0}\le 2x$ by (15). Our games, however, are {\it succinct\/}, i.e., the input size is $\Omega(\log x)$ rather than $\Omega(x)$ (assuming that $y$ is bounded by a polynomial in $x$). Thus their complexity isn't obvious a priori. Even if the sequence $B$ grows exponentially, polynomiality of the strategy doesn't necessarily follow. For example, I don't know whether the sequence $B$ of ${\mathbf G_3}$ can be computed polynomially. Special sequences are known to be computable polynomially. For example, consider the numeration system with bases defined by the recurrence $u_n=(s+t-1)u_{n-1}+su_{n-2}\ (n\ge 1)$, where $s, t\in\IZ_{>0}$, with initial conditions $u_{-1}=1/s$, $u_0=1$. It follows from \cite{Fra1985} that every positive integer $N$ has a unique representation of the form $N=\sum_{i\ge 0} d_iu_i$, with digits $d_i\in\{0,\dots,s+t-1\}$, such that $d_{i+1}=s+t-1\Longrightarrow d_i2$. There is also the notion of {\it program complexity\/} \cite{Dal1973}, \cite{Dal1974}, \cite{Dal1975} concerning the complexity of computing a sequence, which is related to Kolmogorov complexity \cite{Kol1968}. \vskip 30pt \section*{\normalsize 7. Epilogue} We have defined an infinite class of 2-pile subtraction games with two types of moves: (aaa) remove any positive number from a single pile; (bbb) remove $k>0$ from one pile, $\ell>0$ from the other. This move is restricted by the requirement $|k-\ell|