\documentclass[12pt]{article}
\textwidth= 6.25in \textheight= 8.5in \topmargin = -10pt
\evensidemargin=10pt \oddsidemargin=10pt \headsep=25pt
\parskip=10pt
\newcommand{\misere}{mis\`{e}re }
\def \void#1{}
\usepackage{amsmath,amsthm,latexsym,amssymb}
\font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9
%%\def\text{\rm}
\def\refeq#1{\if\workingver y(\ref{#1})-[[#1]]\else(\ref{#1})\fi}
\def\refth#1{\if\workingver y\ref{#1}-[[#1]]\else\ref{#1}\fi}
\def\mylabel#1{\if\workingver y\label{#1}{\bf\ \ [[#1]]\ \ }
\else\label{#1}\fi}
\def\mybibitem#1{\if\workingver y\bibitem{#1}{\bf\ \ [[#1]]\ \ }
\else\bibitem{#1}\fi}
\newtheorem{thm}{Theorem}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{defn}[thm]{Definition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{ex}[thm]{Example}
\newtheorem{algo}[thm]{Algorithm}
\newtheorem{rem}[thm]{Remark}
\newtheorem{conj}[thm]{Conjecture}
%\newenvironment{proof}[1][Proof]{\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\renewcommand{\baselinestretch}{1.1}
\begin{document}
\vspace*{-60pt}
\centerline{\smalltt INTEGERS:
 \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 4
(2004), \#G03}
\vskip 30pt
\begin{center}
{\bf PILESIZE DYNAMIC ONE-PILE NIM AND BEATTY'S THEOREM} \vskip
20pt
{\bf Arthur Holshouser}\\
{\smallit 3600 Bullard St.,
 Charlotte, NC 28208,  USA}
\vskip 20pt
{\bf Harold Reiter}\\
{\smallit Department of Mathematics,
University of North Carolina Charlotte, 
Charlotte, NC 28223, USA}\\
{\tt hbreiter@email.uncc.edu}
\vskip 20pt
{\bf James Rudzinski} \\
%\footnote{any footnote here}}\\
{\smallit Department of Mathematics, Emory University, Atlanta, GA
30322, USA}\\ {\tt jerudzin@yahoo.com}\\ %(optional)
\end{center}


{ \vskip 30pt \centerline{\smallit Received:  12/16/03, 
Revised: 5/20/04, Accepted:
5/26/04,
Published: 5/31/04 } \vskip 30pt}

\centerline{\bf Abstract} \noindent In \cite{Beattys} we proved a
 generalization of Beatty's Theorem which we stated came from
 the Nim value analysis of a game.  In this paper we give the
 Nim value analysis of this game and show its relationship with Beatty's
 Theorem.
The game is a  one-pile counter pickup game for which the maximum
number of counters that can be removed on each successive move
changes during the play of the game. The move size is bounded by a
move function $f$ whose arguments are pile sizes. After analyzing
this game, we discuss a blocking version of this game  as well as
the mis\`{e}re version.

\pagestyle{myheadings} \markright{\smalltt INTEGERS:
\smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY
\smalltt 4 (2004), \#G03\hfill}

\thispagestyle{empty}
%\baselineskip=15pt \vskip 30pt
 \void{ Your
paper starts here with your first section. See III below for more
information on how to number sections.}




%\thispagestyle{empty} \baselineskip=15pt \vskip 30pt


\void{ III. In the body of the paper, please follow A, B, and C
below. A. Label and number your (sub)sections as follows.
"\section*{\normalsize N. Section Name}", where N=1,2,...
corresponds to the section number. and/or
"\subsection*{\normalsize N.x Subsection Name}", where N=1,2,3,...
and x=1,2,3,... correspond to the subsection number. B. After the
end of each section and before the beginning of the next section
please put the line:}

\void{ C. Please label your Definitions, Lemmas, Theorems, etc. in
the format "{\bf Theorem x}" where x is how you see fit. Further,
denote the start of your proofs by {\it Proof.}}



\section*{\normalsize 1. Introduction}
Two players alternately remove a positive number of counters from
a pile of counters. The maximum size of the move is determined by
a move function $f:N\rightarrow N$ whose arguments are pile sizes.
Each player in his turn must remove from one up to the minimum of
$n$ and $f(n)$ counters, where $n$ is the size of the pile. The
game ends when either the pile is empty or $f(n)=0$ and the winner
is the last player to move. Since we can replace a move function
$f(n)$ with $\min(n,f(n))$ without changing the legal moves in the
game, without loss of generality we will assume $0\le f(n)\le n$
throughout the paper.
 Our analysis
solves a very large class of games that includes as a subclass all
games whose move function satisfies both
\begin{enumerate}
\item $f(0)=0$ and
\item For all $n\ge 0,\,  f(n+1)-f(n)\in \{0,1\}.$
\end{enumerate}
The second condition, called the {\bf unit jump condition} (ujc),
will be used repeatedly.

The move functions $f(n)=\lfloor rn\rfloor $ and $f(n)=\lceil
rn\rceil $ for some $r,\  0<r\le 1$, are primitive special cases.
Our analysis using $f(n)=n$ solves both the regular and \misere
versions of $m$-pile Bouton's nim. Also, our analysis using
$f(n)=\min(n,k), k=1,2,\ldots $ solves both the regular and
\misere versions of $m$-pile modular Bouton's nim.

At the end of this paper, we will show how to generate numerous
examples of the game.   These will include the `primitive' move
functions $f(n)=\lfloor rn \rfloor $ and $f(n)=\lceil rn\rceil,
0<r\le 1.$ In Example 1 immediately after Lemma 6,  we show how
the analysis in this paper also generalizes Beatty's Theorem.
\void{Beatty's Theorem deals with the partitioning of the positive
integers into two sets, which we will also discuss further in
Section 4.}  In a companion paper \cite{Beattys}, we used the same
basic analysis as we do here to extend Beatty's Theorem to
strictly increasing continuous functions that are independent. See
\cite{Beatty} and \cite{Lam}. Also, a further extension of this
paper led us to discover a class of combinatorial games that we
have not seen in the literature. We call these blocking games, and
we discuss the blocking version of this game briefly in Section 6.
See \cite{Flam}.

\void{ Next we provide the reader with a short summary of the
motivation for this paper. We started by studying the Nim values
for the simple move function $f(n)=\lfloor n/2 \rfloor$. Then we
noticed that this function satisfies the unit jump condition, and
that most of our conclusions hold for all move functions
satisfying the ujc. Later we were able to extend our results for
functions that do not satisfy the ujc. However, we have not been
able to find both necessary and sufficient conditions on $f$ so
that our methods are effective. We also added Theorem 4 to make
the proofs more efficient, since we were writing the same proofs
repeatedly. We then proceeded naturally to solve other related
problems  such as finding and classifying in different ways  all
possible Nim-value sequences $g(1), g(2), g(3), \ldots $ that can
exist  when $f(n)$ satisfies the ujc.}

This paper uses the Sprague-Grundy theory of combinatorial games
which we summarize below. The Grundy values of positions, which we
denote $g(n)$, are called Nim values in this paper. Sections 2 and
3 can be omitted by those readers who are familiar with this
material.

\section*{\normalsize 2. Beatty's Theorem}
In 1926 Sam Beatty made the following discovery, which he posed as
a  problem in \cite{Beatty}. If $a$ is a positive irrational
number, the sequences $m(1+a), m=1,2,\ldots$ and $n(1+a^{-1}),
n=1,2,\ldots$ together contain exactly one number from each of the
intervals $(k,k+1), k=1,2,\ldots$.



\section*{\normalsize 3. Impartial Games}
 Our
game is a finite, impartial game played under the usual rules of
play:
\begin{enumerate}
\item two players alternate moving,
\item there is no infinite sequence of moves,
\item both players have the same moves available, and
\item the winner is the last player to make a move.
\end{enumerate}
Such a game can be thought of a directed acyclic graph. Each
vertex of the graph corresponds to a position in the game, and the
directed edges correspond to the possible moves. The
\textit{followers} of a vertex are those positions joined by an
outgoing edge.

The {\em minimum excluded value} (mex) of a finite set of
nonnegative integers is the least nonnegative integer not in the
set. For example, $mex\{1,2,4,0\}=3$ and $mex\{\quad \}=0$. The
Nim value of a position is the mex of the nim values of its
followers. A position with no followers (a terminal position) has
Nim value 0. It is easy to see that the winning strategy is to
move to a position with Nim value 0, for then the opponent either
has no move at all and loses immediately, or must move to a
position with Nim value greater than 0, and so must eventually
lose.

Nim values are of greatest use in {\em composite} games where
there are several components. Each player, on his turn,  selects a
component game in which a legal move can be made and makes a legal
move in that game. The game is over when no legal moves can be
made in any of the component games, and the winner is the player
who makes the last move.  The Nim value of the composite game is
the nim sum $\oplus$ of the Nim values of the component games. The
nim sum is obtained by writing the integers in binary and adding
modulo 2 without carrying. For example, $2\oplus 3=10_2\oplus
11_2=01_2=1$.

The positions $(P_1,P_2, \ldots, P_k)$ with a nim sum of zero
($g(P_1)\oplus g(P_2)\oplus \ldots \oplus g(P_k)=0$) are called
\emph{balanced }positions, and the positions with a non-zero nim
sum are called \emph{unbalanced}. A player who moves from an
unbalanced position can always move to a balanced position, but a
player who moves from a balanced position must always move to an
unbalanced position.  Note that all terminal positions are
balanced. The mis\`{e}re version of the game is played under the
same rules except that the \textbf{loser} is the last player to
make a move. Let us call a component game $G_i$ \emph{special} if
for each non-terminal position $P$ in $G_i$ such that $g(P)=0$,
 there is a follower $Q$ of $P$ with $g(Q)=1$. If each
component $G_i$ is special, then the balanced positions
$(P_1,P_2,\ldots, P_k)$ in the mis\`{e}re version of the composite
game are given by the following two conditions:
\begin{enumerate}
\item If at least one $g(P_i)\ge 2$, then $(P_1,P_2,\ldots, P_k)$
is balanced if and only if $g(P_1)\oplus g(P_2)\oplus \ldots
\oplus g(P_k)=0$.
\item If each $g(P_i)\in \{0,1\}$, then $(P_1,P_2,\ldots, P_k)$ is
balanced if and only if $g(P_1)\oplus g(P_2)\oplus \ldots \oplus
g(P_k)=1$. \end{enumerate} All the other positions are unbalanced.
Note that all the terminal positions are unbalanced. We point out
later  that all of the games studied in this paper are special.









\section*{\normalsize 4. Main Theorems}
We now proceed to solve the subclass of games mentioned above.
This is followed by an extension of the solution to the entire
class of games. Let $N$ denote the set of non-negative integers
and $Z$ the set of all integers.




\par \noindent
\begin{thm}%%%Theorem  1.
 Let $n$ be a non-negative integer. Consider the game \newline
 $(n,f)$ where $n$ is the pile size and  $f:N\rightarrow N$ is
a move  function such that $f(0)=0$ and $f$ satisfies the ujc.
Then the Nim values $g(n)$ in the game $(n,f)$ satisfy the
following:
\begin{enumerate}
\item $g(0)=0$
\item If ${f}(n)-{f}(n-1)=1$ and $n\ge 1$, then $g(n)={f}(n)$.
\item If ${f}(n)-{f}(n-1)=0$ and $n\ge 1$,
then  $g(n)=g(n-1-f(n))$.
\item For all non-negative integers $n$,
$\{g(n), g(n-1), \ldots, g(n-{f}(n))\}=\\
\{0,1,2, \ldots , {f}(n)\}$, where $0<1< \ldots < {f}(n)$
{\rm(that is, the elements of the set} $\{0,1,2, \ldots ,
{f}(n)\}$ {\rm are listed exactly once).}
\item For all non-negative integers $n$,
$g(n)\le {f}(n)$.
\end{enumerate}
\end{thm}




\begin{proof}
As noted above, ${f}(n)\le n$ for all $n \in N$.
 The proof of the theorem is by mathematical induction on $n$.
Starting the induction at $n=0$ is trivial because only conditions
1, 4 and 5 apply, which hold because $g(0)= {f}(0)=0$. Now assume
that the theorem holds for $k\in \{0,1,2,\ldots, n-1\}$. We show
that the statements also hold for $n$. Since $f$ satisfies ujc,
either
\newline Case 1. $ {f}(n-1)+1=f(n)$ or
\newline Case 2.  ${f}(n-1)=f(n)$.
\newline
We will tacitly assume that $f(n)>0$. If $f(n)=0$, then
${f}(0)={f}(1)={f}(2)= \ldots ={f}(n)=0$ since $f$ is
non-decreasing.
\newline
Proof for case 1. The condition can be rewritten as  $ {f}(n)-
{f}(n-1)=1$. Thus we need to prove condition 2. Once we prove
condition 2, it is clear that condition 5 also holds. From
condition 4 and the induction hypothesis, $\{g(n-1),
g(n-2),\ldots, g(n-1- {f}(n-1))\}= \{0,1,2, \ldots, {f}(n-1)\}$,
where $0<1<\cdots <
 {f}(n-1)$. Then from the definition of Nim value,
\begin{eqnarray*}
\lefteqn{g(n)=mex (\{g(n-1), g(n-2),\ldots, g(n-f(n))\})}\\
&=& mex (\{g(n-1), g(n-2),\ldots, g(n-1- {f}(n-1))\}) \\
&=& mex (\{0,1,2\ldots,
 {f}(n-1)\}=f(n-1)+1=f(n). \\
\end{eqnarray*}

\void{We ignore the expression on the right when ${\varepsilon}=0$
Note that $0\le g(n-1- {f}(n-1)-i)\le
 {f}(n-1- {f}(n-1)-i)\le  {f}(n-1)$ by the
induction hypothesis about  condition 5 of the theorem and the
fact that $ {f}$ is non-decreasing. Thus $g(n-1- {f}(n-1)-i)$ lies
in the set $\{0,1,\ldots,  {f}(n-1)\}$. From the definition of
$mex$ it follows that $g(n)= {f}(n-1)+1=  {f}(n)$.}


 To prove
condition 4, note that
\begin{eqnarray*}
\lefteqn
{\{g(n), g(n-1), g(n-2),\ldots, g(n- {f}(n))\}}\\
&=&\{g(n),g(n-1),\ldots, g(n-1- {f}(n-1))\}\\
&=& \{g(n)\}\cup \{g(n-1), g(n-2),\ldots, g(n-1- {f}(n-1))\}\\
&=& \{ {f}(n)\}\cup \{0,1,2,\ldots,  {f}(n-1)\}\\
&=& \{0,1,2,\ldots,  {f}(n)\}, \mbox{ where } 0<1<\cdots <
 {f}(n),
\end{eqnarray*}
since $0<1<\ldots < {f}(n-1)$ and $ {f}(n-1)< {f}(n)$.



Proof for case 2.  We are given $f(n-1)= {f}(n).$  Thus we need to
show
 condition 3, namely, $g(n)=g(n-f(n)-1)$. First we need to make
 sure that $n-f(n)-1\ge 0$. But $0\le f(n-1)\le n-1$ was assumed
 previously and from $f(n-1)\le n-1$ and $f(n)=f(n-1)$, it follows
 that $n-f(n)-1\ge 0$.
The induction hypothesis gives $\{g(n-1), g(n-2),\ldots,
g(n-1-{f}(n-1))\}=
 \{0,1,2,\ldots {f}(n-1)\}$ where $0<1<\cdots < {f}(n-1)$.
  Therefore,
\begin{eqnarray*}
\lefteqn{g(n)=mex (\{g(n-1), g(n-2),\ldots, g(n-f(n))\})}\\
&=&  mex (\{g(n-1), g(n-2),\ldots, g(n-{f}(n-1))\})\\
&=&  mex (\{g(n-1), g(n-2),\ldots, g(n-1-{f}(n-1))\}
\backslash\{g(n-1-{f}(n-1))\})\\
&=& mex (\{0,1,2,\ldots
{f}(n-1)\}\backslash\{g(n-1-{f}(n-1))\}), \\
&=&g(n-1-{f}(n-1))=g(n-1-{f}(n))\mbox{ (from the definition of
$mex$)},
\end{eqnarray*} which proves condition 3.


 Next note that
  $g(n)=g(n-{f}(n)-1)\le
  {f}(n-{f}(n)-1)\le{f}(n)$
  by the induction hypothesis with condition 5 and the fact that
  ${f}$ is non-decreasing. So condition 5 holds.


Furthermore, condition 4 is satisfied:
\begin{eqnarray*}
\lefteqn{ \{g(n), g(n-1), g(n-2),\ldots, g(n-{f}(n))\}}\\
&=&  \{g(n), g(n-1), g(n-2),\ldots, g(n-{f}(n-1))\}\\
&=&  \{g(n)\}\cup \{g(n-1), g(n-2),\ldots, g(n-{f}(n-1))\}\\
&=&   \{g(n-1-{f}(n-1))\}\cup \{g(n-1), g(n-2),\ldots,
 g(n-{f}(n-1))\}\\
 &=&   \{g(n-1), g(n-2),\ldots,
 g(n-1-{f}(n-1))\}\\
&=& \{0,1,2,\ldots {f}(n-1)\} %, 0 <1<2<\ldots < {f}(n-1),
\\ &=& \{0,1,2,\ldots
{f}(n)\}
\end{eqnarray*}
since ${f}(n)={f}(n-1)$.
\end{proof}
\bigskip

Readers who are mostly interested in Beatty's Theorem can skip
Theorem 2 since it can be omitted without loss of continuity. Now
we expand the result of Theorem 1 as follows.
 First we need some notation. Let
$h$ be a function from the nonnegative integers $N$ to the
integers $Z$. Define the \textit{derived function}
$h':N\rightarrow Z$ as follows: $h'(0)=0$ and for $n\in N
\setminus \{0\}, \ h'(n)=\min(h'(n-1)+1, h(n))$. Suppose $h(0)=0$
and $h$ satisfies the ujc, as required in the hypothesis of
Theorem 1. Then it follows by mathematical induction that $h=h'$.
Also note that $h'$ satisfies the ujc if and only if $h'$ is
non-decreasing. The following illustrates a move function $f$ such
that the derived function $f'$ is non-decreasing. Note that
$(f')'=f'. $\newline \vspace{.1in}
  \centerline{
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|} \hline
    $x$&0&1 &2&3&4&5&6&7&8 \\ \hline
 $f(x)$&0&3&4&4&4&4&8&7&6     \\ \hline
 $f'(x)$& 0&1 &2&3&4&4&5&6&6    \\ \hline
\end{tabular}}
\bigskip

\begin{thm}  %theorem 2
The games $(n,f)$ and $(n,f')$ have the same Nim values for any
move function $f: N\rightarrow N$ such that $f'$ is
non-decreasing.
\end{thm}
Thus the class of functions for which we can solve the game is
enlarged to all games $(n,f)$ such that the derived function $f'$
satisfies the hypothesis of Theorem 1, a much larger class of
games.
\begin{proof}
The proof is by induction. The base case: $g((0,f))=g((0,f'))=0$
since these are both terminal positions. Now suppose
$g((k,f))=g((k,f'))$ for $0\le k\le n-1$.
  To see that
$g((n,f))=g((n,f'))$, we consider the two cases a)
$f'(n)-f'(n-1)=0$ and b) $f'(n)-f'(n-1)=1$. In case a) it follows
from the definition of $f'$ that $f'(n)=f(n)$. Then
\begin{eqnarray*}
 g((n,f))&=&mex (\{g(n-1),g(n-2), \ldots, g(k-f(n))\})\\
&=&mex(\{g(n-1),g(n-2), \ldots, g(n-f'(n))\})=g((n,f')).
\end{eqnarray*}
On the other hand, in case b), from Theorem 1, $g((n,f'))=f'(n)$.
%%%start here
Then $g((n,f'))=mex(\{g(n-1),g(n-2), \ldots, g(n-f'(n))\})=f'(n)$.
But applying condition 4 from Theorem 1 yields
$\{g((n,f')),g(n-1),g(n-2), \ldots, g(n-f'(n))\})=\{0,1,2,\ldots ,
f'(n)\} $, so $\{g(n-1),g(n-2), \ldots,
g(n-f'(n))\})=\{0,1,2,\ldots , f'(n)-1\}=\{0,1,2,\ldots ,
f'(n-1)\} $. Now $g((n,f))=mex (\{g(n-1),g(n-2), \ldots,
g(n-f(n))\})$.  Since $f(n)\ge f'(n)$, this is equal to $$\\ mex (
\{g(n-1),g(n-2), \ldots, g(n-f'(n))\}\cup
\{g(n-1-f'(n)),g(n-2-f'(n)), \ldots, g(n-f(n))\})
$$
$$=mex (
\{0,1,2,\ldots, f'(n-1))\}\cup \{g(n-1-f'(n)),g(n-2-f'(n)),
\ldots, g(n-f(n))\})$$ \par But $0\le g(n-i-f'(n))\le
f'(n-i-f'(n))\le f'(n-1)$ for $i\in \{1,2,\ldots, f(n)-f'(n)\}$ by
condition 5 of Theorem 1 and the fact that $f'$ is non-decreasing.
Thus each $g(n-i-f'(n))$ lies in the set $\{0,1,2,\ldots ,
f'(n-1)\}$ and therefore we have $g(n,f)=mex (\{0,1,2,\ldots,
f'(n-1)\})=f'(n-1)+1=f'(n)$, as was to be shown. Thus
$g((n,f))=g((n,f'))$ in either case, and this completes the
inductive proof.
\end{proof}
\par
 In order to use
Theorem 1 more effectively with specific functions,  we need
Theorem 4, which generalizes Theorem 1. We also use the functions
$F(m),H(m)$ of Definition 3 when we generalize Beatty's Theorem.
\par
\begin{defn}
 For any  non-negative integer $n$, consider the game $(n,f)$
 where the
move  function $f$ satisfies the four conditions
\begin{enumerate}
\item $f(0)=0$ and
\item For all $n\ge 0,\,  f(n+1)-f(n)\in \{0,1\}.$
\item $\lim_{n\rightarrow \infty}f(n)=\infty$.
\item $\lim_{n\rightarrow \infty}n-f(n)=\infty$.
\end{enumerate}
Let $h(n)=n-f(n)$. Note that because of conditions 1-4, both $h$
and $f$ are surjections of $N$ onto $N$. Thus for each integer
$m\ge 0$, we may define  $F(m)$ to be the smallest non-negative
integer $x$ such that $f(x)=m$, and $H(m)$ to be the smallest
non-negative integer $x$ such that $h(x)=m$. Finally, let $\alpha$
be any non-negative integer and $0\le a_1 < a_2 \cdots < a_i <
\cdots$ be all the non-negative integers such that
$g(a_i)=\alpha$. That is, $a_1, a_2, \ldots$ is the sequence of
pile sizes whose Nim values are $\alpha$.
\end{defn}

\begin{thm} %theorem 4
The sequence $a_1, a_2, \ldots$ can be generated recursively as
follows: $a_1=F(\alpha)$ and for all $i=2,3,4, \ldots,\quad
a_i=H(a_{i-1}+1)$.  \end{thm}

The conditions 3 and 4 could be omitted, but the proof would be
slightly more technical.

\begin{proof} First note that
\begin{enumerate}
\item $h(0)=0$,
\item for all $n\ge 0,\,  h(n+1)-h(n)\in \{0,1\}$, and
\item $\lim_{n\rightarrow \infty}h(n)=\infty $.
\end{enumerate}
 We use
Theorem 1 to prove Theorem 4 by induction on the index $i$ in
$a_1, a_2, \ldots$.  Since $\lim_{n\rightarrow \infty}f(n)=\infty$
and  $\lim_{n\rightarrow \infty}n-f(n)= \lim_{n\rightarrow
\infty}h(n)=\infty$, we can use conclusion 2 once and conclusion 3
repeatedly to show that for all nonnegative integers $\alpha$
there are infinitely many nonnegative integers whose Nim value is
$\alpha$. Therefore it makes sense to talk about $a_1, a_2,
\ldots$ as being the infinite  increasing sequence of all
non-negative integers whose Nim values are $\alpha$. Since  $h$
and $f$ satisfy  the ujc,
 it follows that
$f(F(m)-1)=m-1$ for all $m\ge 1$ and $h(H(m)-1)=m-1$ for all $m\ge
1$.
\par From condition 5 of Theorem 1, it follows that for all $n\ge
0, \quad g(n)\le f(n).$ Therefore, from condition 2 of Theorem 1,
$a_1=F(\alpha)$. Thus we may suppose for the induction hypothesis
that $0\le a_1=F(\alpha)<a_2<a_3<\ldots < a_i$ are all the
non-negative integers up to and including $a_i$ whose Nim values
are $\alpha$. We also suppose that these $a_i$'s are generated by
$a_1=F(\alpha)$ and $a_k=H(a_{k-1}+1)$ for all $k\in \{2,3,\ldots,
i\}$.

To complete the proof it remains to show that the next positive
integer $a_{i+1}$ whose Nim value is $\alpha$ is given by
$$a_{i+1}=H(a_i+1).$$ To this end, let $s$ be the
smallest positive integer such that $h({s})>a_i$. Of course,
$s=H(a_i+1)$. Also, $a_i< s  $ since $h(n)\le n$. Since
$h(n+1)-h(n) \in \{0,1\}$, we have
 $$\mbox{i.} \quad
 s  -f( s  )=a_i+1 \mbox {\hspace{.1in} and \hspace{.1in} ii.} \quad
 ( s  -1)-f( s  -1)=a_i.$$

 We ignore this paragraph when $a_i= s  -1$ because in this case  the sets are empty.
   The condition $h(n+1)-h(n) \in
\{0,1\}$ together with equation ii.
 above implies that for all
$t\in \{a_i+1, a_i+2,\ldots,s-1\},  h(t)=t-f(t)\le a_i$.
Therefore, for $t\in \{a_i+1,a_i+2, \ldots,  s-1\}$,  $a_i\in
\{t-1,t-2, t-f(t)\}$. Therefore, $g(a_i)=\alpha \in
\{g(t-1),g(t-2), \ldots, g(t-f(t))\}$, and for $t$ in the above
range, $g(t)=mex\{g(t-1),g(t-2), \ldots, g(t-f(t))\}\neq \alpha$.

 We now show that $g( s  )=\alpha$.
This will complete the proof since $ s  $ is the next integer
after $a_i$ such that $g( s  )=\alpha$ and $ s  =H(a_i+1)$. Using
equations i. and ii.
 above, we see that $f( s )-f( s  -1)=0$. From
conclusion 3 of Theorem 1 and equation i.  above, we see that $g(
s  )=g(s -f( s  )-1)=g(a_i)=\alpha$.
\end{proof}

In order to apply Theorem 4, we will use the following material
from the companion paper \cite{Beattys}.


\begin{defn}  Suppose $u, v$ are real functions on the domain
$[0,\infty)$. We say $u$ and $v$ are complementary if they satisfy
\begin{enumerate}
\item $u(0)=v(0)=0$,
\item $u$ and $v$ are non-decreasing on $[0,\infty)$, and
\item $u(x)+v(x)=x$ for all nonnegative  $x$.
\end{enumerate}
\end{defn}

It is easy to see that at least one of $u$ and $v$ is unbounded.
As a technical convenience, we assume both are unbounded. It is
easy to see that $\forall \epsilon > 0, \forall x \in [0,\infty),
\\  0\le u(x+\epsilon)-u(x)\le \epsilon \mbox{ and } 0\le
v(x+\epsilon)-v(x)\le \epsilon$. From this it follows that both
$u$ and $v$ are continuous.

\begin{lem} Suppose $u$ and $v$ are complimentary functions.
Define $f:N\rightarrow N,$
\newline  $h:N\rightarrow N$ by $f(n)=\lfloor u(n)\rfloor,
h(n)=n-f(n)=n-\lfloor u(n)\rfloor=\lceil n-u(n)\rceil=\lceil
v(n)\rceil$. Since $f$ and $h$ satisfy the conditions of
Definition 3, for every nonnegative integer $m$, $F(m)$ and $H(m)$
are defined by Definition 3. For any nonnegative integer $m$,
define $u^{-1}(m)$ to be the {smallest} nonnegative real number
that satisfies $u(u^{-1}(m))=m$ and $v^{-1}(m)$ to be the
{largest} nonnegative real  number satisfying $v(v^{-1}(m))=m$. .
Then $F(m)=\lceil u^{-1}(m) \rceil$, and  $H(0)=0, H(m+1)=\lfloor
v^{-1}(m)+1\rfloor$.
\end{lem}

\begin{proof} We prove that $\forall m\in
\{0,1,2,\ldots\}$, (1) $F(m)=\lceil u^{-1}(m)\rceil$.  The proof
that (2) $H(0)=0,
 H(m+1)=\lfloor v^{-1}(m)+1 \rfloor$ is very similar and is left
 to the reader. An intuitive proof of (1) and (2) using pictures
 is also fairly easy. Formal proofs of these are also given in
 \cite{Beattys}, where we assume that both $u$ and $v$ are
 strictly increasing. Considering $m\in \{0,1,2,\ldots\}$ to be
 fixed, we abbreviate $u^{-1}(m)$ as $u^{-1}$. Thus $u^{-1}$ is
 the smallest non-negative real number for which $u(u^{-1})=m$.
 Also, define $\overline{u}=\lceil u^{-1}\rceil$. Now it is easy to see that
 $F(0)=\lceil
 u^{-1}(0)\rceil=0$. Therefore, we assume $m\in \{1,2,3,\ldots\}$.
 Note that $u^{-1}(m)=u^{-1}\ge 1$ since $\forall x \in [0,
 \infty), 0\le u(x)\le x$.
 Since $f$ satisfies the ujc, equality (1) is assured once we
 prove
 \begin{enumerate}
 \item[a.] $f(\overline{u})=\lfloor u(\overline{u})\rfloor=m$, and
 \item[b.] $f(\overline{u}-1)=\lfloor u(\overline{u}-1)\rfloor=m-1.$
\end{enumerate}
To prove a. note that $\overline{u}-u^{-1}=\overline{\epsilon},$
where $0\le \overline{\epsilon} <1$. Then \begin{eqnarray*}
\lfloor u(\overline{u})\rfloor&=&\lfloor
u(u^{-1}+\overline{\epsilon})\rfloor\\
&=&\lfloor u(u^{-1}+\overline{\epsilon})-u(u^{-1})+u(u^{-1})\rfloor \\
&=&\lfloor u(u^{-1}+\overline{\epsilon})-u(u^{-1})+m\rfloor \\
&=&m+\lfloor u(u^{-1}+\overline{\epsilon})-u(u^{-1})\rfloor.
\end{eqnarray*}
Also, $0\le u(u^{-1}+\overline{\epsilon})-u(u^{-1})\le
\overline{\epsilon}<1$. Therefore, $\lfloor
u(u^{-1}+\overline{\epsilon})-u(u^{-1})\rfloor =0$. Thus $\lfloor
u(\overline{u})\rfloor=m+\lfloor
u(u^{-1}+\overline{\epsilon})-u(u^{-1})\rfloor=m$. To prove (b),
define $\underline{u}=\overline{u}-1=\lceil u^{-1}-1\rceil$. Let
$u^{-1}-\underline{u}=\underline{\epsilon}$, where $ 0<
\underline{\epsilon} \le 1$. Now $\lfloor
u(\overline{u}-1)\rfloor=\lfloor u(\underline{u})\rfloor=\lfloor
u(u^{-1}-\underline{\epsilon})\rfloor =\lfloor
u(u^{-1}-\underline{\epsilon})-u(u^{-1})+u(u^{-1})\rfloor=\lfloor
u(u^{-1}-\underline{\epsilon}) -u(u^{-1})\rfloor+m$. Since $u$ is
non-decreasing and $u^{-1}=u^{-1}(m) $ is the smallest
non-negative real number satisfying $u(u^{-1})=m$ and $0<
\underline{\epsilon}$, it follows that
$0<u(u^{-1})-u(u^{-1}-\underline{\epsilon})\le
\underline{\epsilon}\le 1$. Therefore, $-1\le
u(u^{-1}-\underline{\epsilon})-u(u^{-1})<0$. Therefore, $\lfloor
u(u^{-1}-\underline{\epsilon})-u(u^{-1})\rfloor=-1$. Thus $\lfloor
u(\overline{u}-1)\rfloor=\lfloor
u(u^{-1}-\underline{\epsilon})-u(u^{-1})\rfloor +m=m-1$.
\end{proof}

The reader can easily see that the two sequences $F(m),
m=1,2,3,\ldots$, and $H(m+1),\ m=0,1,2,3, \ldots$ together
partition the set of positive integers and also that the members
of each of the two sequences are distinct. This result is a
generalization of Beatty's Theorem. In \cite{Beattys}, we extend
this  in a natural way to achieve a more powerful version of this
result in which the continuous, increasing functions $u$ and $v$
are completely independent.

\section*{\normalsize 5. Examples}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%start here

 \textbf{Example 1 (Beatty's Theorem)} Define
$u(x)=\frac{x}{1+a}$ and $v(x)=\frac{ax}{1+a}, a>0$. From lemma 6,
$F(m)=\lceil u^{-1}(m)\rceil =\lceil (1+a)m\rceil$ and
$H(m+1)=\lfloor v^{-1}(m)+1\rfloor=\lfloor (1+1/a)m+1\rfloor$. We
know that $F(m), m=1,2,\ldots,$ and $H(m+1), \ m=0,1,2, \ldots,$
together partition the set of positive integers and the members of
each of the  two sequences are distinct. Since $H(0+1)=1$, it
follows that $F(m),\ m=1,2,\ldots$ and $H(m+1), \ m=1,2,\ldots$
partitions $\{2,3,4, \ldots\}$. Now if $a$ is irrational, then
$H(m+1)=\lceil (1+1/a)m\rceil$. Therefore, if $a$ is irrational,
then the sequences  $\lceil(1+a)m\rceil,\  m=1,2,\ldots$ and
$\lceil(1+1/a)m\rceil, \ m=1,2,\ldots$ partition $\{2,3,\ldots
\}$, which is equivalent to Beatty's Theorem.


  The original solution to Beatty's problem was provided
   by Ostrowski and Aitken \cite{Ost} and
generalized to a larger class of sequences by Lambek and Moser
\cite{Lam}. It appears that the Lambek and Moser approach is the
inverse of our approach. Our approach arose from studying the Nim
(ie, Sprague-Grundy) values of games, while it is quite possible
that Lambek and Moser were not aware of connection with
combinatorial games. In \cite{Fraenkel}, Fraenkel used Beatty's
Theorem to study a generalized Wythoff's game. He did not use
Wythoff's game to derive Beatty's Theorem as we have done here
with our game.




\textbf{Example 2.} Define $u, v$ on $[0,\infty)$ as follows:
$$u(x)=\left\{
\begin{array}{ll}
        x & \mbox{if $0\le x\le 1$} \\
        \sqrt x   & \mbox{if $x>1$}
        \end{array} \right . $$
and $$v(x)=\left\{
\begin{array}{ll}
        0 & \mbox{if $0\le x\le 1$} \\
        x-\sqrt x   & \mbox{if $x>1$}
        \end{array} \right . $$
Define the move function $f(n)=\lfloor \sqrt n\rfloor, n=0,1,2,
\ldots$. Then $h(n)=\lceil n-\sqrt n\rceil, n=0,1,2,\ldots$. We
invite the reader to go through the technicalities of Lemma 6. Now
$u^{-1}(n)=n^2, n=0,1,2,\ldots, $ and
$v^{-1}(n)=\frac{2n+1+\sqrt{4n+1}}{2}, n=0,1,2, \ldots.$ Let $a$
be any nonnegative integer and $0\le a_1<a_2\ldots $ be all of the
nonnegative integers whose Nim values are $a$. Then $a_1,a_2,
\ldots$ is generated recursively as follows: $a_1=F(a)=\lceil
u^{-1}(a)\rceil = a^2$, and for all $i\in \{2,3\ldots, \}, \
a_i=H(a_{i-1}+1)=\lfloor v^{-1}(a_{i-1})+1\rfloor = \left \lfloor
\frac{2a_{i-1}+3+\sqrt{4a_{i-1}+1}}{2}\right \rfloor.$

The reader will also note the following Beatty-like property. The
sequences $F(m)=m^2, \ m=1,2,3,\ldots$ and $H(m+1)=\left \lfloor
\frac {2m+3+\sqrt{4m+1}}{2} \right \rfloor,\ m=0,1,2, \ldots$ are
disjoint sequences of distinct positive integers whose union is
the set of positive integers.

\textbf{Example  3.}
 Define $u, v$ on $[0,\infty)$ as follows:
$$u(x)=\left\{
\begin{array}{ll}
        0 & \mbox{if $0\le x\le 1$} \\
        3x^{2/3}-3x^{1/3}  & \mbox{if $x>1$}
        \end{array} \right . $$
and $$v(x)=\left\{
\begin{array}{ll}
        x & \mbox{if $0\le x\le 1$} \\
        x-3x^{2/3}+3x^{1/3}  & \mbox{if $x>1$}
        \end{array} \right . $$
Define the move function $f(n)=\lfloor 3n^{2/3}-3n^{1/3}\rfloor,
n=0,1,2, \ldots$. Then $h(n)=\\   \lceil
n-3n^{2/3}+3n^{1/3}\rceil, n=0,1,2, \ldots$. Now $u^{-1}(0)=0$,
$$u^{-1}(n)=\left( \frac 12 +\frac 12 \sqrt{1+4n/3}\right)^3, \
n=1,2,3,\ldots,$$ and
$$v^{-1}(n)=\left(1+\sqrt[3]{n-1}\right)^3, \ n=0,1,2,\ldots.$$
 Let
$a$ be any nonnegative integer and $0\le a_1<a_2<\ldots $ be all
the nonnegative integers whose Nim values are $a$. Then $a_1, a_2,
\ldots $ is generated recursively as follows: $a_1=F(a)=\lceil
u^{-1}(a)\rceil$ and for all $i\ge 2, \ a_i=H(a_{i-1}+1)=\lfloor
v^{-1}(a_{i-1})+1\rfloor$.

The reader will also note the following Beatty-like property:
$$F(m)=\left\lceil \left(\frac 12+\frac 12 \sqrt{1+4m/3}\right
)^3\right \rceil,\ m=1,2,3,\ldots$$ and $$H(m+1)=\left \lfloor
\left (1+\sqrt[3]{m-1}\right)^3+1\right \rfloor,\ m=0,1,2,
\ldots$$ are disjoint sets of distinct positive integers whose
union is the set of positive integers. Of course we chose $u$ and
$v$ so that $u^{-1}$ and $v^{-1}$ could be represented in explicit
form. When one or both $u^{-1}$ and $v^{-1}$ cannot be computed in
explicit form, we leave it in implicit form the same way that
 $sin^{-1} x$ is left in implicit
form. The reader might also like to consider the following
variations of the above example: $f(n)=\lceil \sqrt n \rceil$,
$f(n)=\lceil n-\sqrt n\rceil$, $f(n)=\lfloor n-\sqrt n\rfloor$,
$f(n)=\lceil rn\rceil, 0<r<1, f(n)=\lfloor rn\rfloor, 0<r<1$,
$f(n)=\lceil 3n^{2/3}-3n^{1/3}\rceil$. The cases where $r=k/(k+1)$
are especially interesting because they can be solved explicitly.
Of course, the Beatty-like property will immediately follow as
well.




\section*{\normalsize 6. Mis\`{e}re  and Blocking Games}
It is easy to see that all the games studied so far are special
games as defined in section 3. Therefore, the mis\`{e}re versions
of the composite games are solved by the strategy given in section
3.


\textbf{Games with Blocking.} Consider the game $(n,f)$ that
satisfies the hypothesis of Theorem 1. Let $k$ denote a
non-negative integer. On each move including the first, before the
moving player moves, the opposing player can block up to $k$ of
the moving players options. We denote this game by $(n,f,k)$. The
nim values of $(n,f,k)$ can be computed by the formula
$$ g(n,f,k)=\left \lfloor \frac{g(n,f)}{k+1}\right \rfloor.$$



\begin{thebibliography}{99}
\footnotesize
\bibitem{Beatty} Sam Beatty,  Problem 3173, {\em American Mathematical Monthly},
 vol. 33, 1926, p.159.

\bibitem{Flam} Flammenkamp, Achim, A. Holshouser,  and H. Reiter,
 Dynamic One-Pile Blocking Nim,
 {\em Electronic Journal of Combinatorics}, Volume 10(1), 2003.




\bibitem{Fraenkel} Fraenkel, A. S. How to beat your Wythoff games' opponents on three fronts,
{\em American Mathematical Monthly}, vol.  89, 1982, pp. 353-361.




\bibitem{Beattys} Holshouser, A. and H. Reiter, An Extention of Beatty's Theorem,
{\em Southwest Journal of Pure and Applied Mathematics}, Issue 2,
December, 2001 pp.24-29.


\bibitem{DOPN} Holshouser, A.,  H. Reiter, and  J. Rudzinski,  Dynamic One-Pile Nim,
{\em Fibonacci Quarterly}, vol 41.3, June-July, 2003, pp 253-262.



\bibitem{Lam} Lambek, J. and L. Moser,\  "Inverse and Complementary Sequences of
Natural Numbers", {\em American Mathematical Monthly}, vol. 61,
1954, p.454.  MR 16,17a.

\bibitem{Ost}  Ostrowski and Aitken, Solution to Problem 3173, {\em American Mathematical
Monthly}, vol. 34, p. 159.

\end{thebibliography}


\end{document}