\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_i~~2$. 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|~~