\documentclass[12pt]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{amsfonts}
\usepackage{amstext}
\usepackage{amssymb,amsmath}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\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 
\title{Variations on a Theme of Euclid}
\author{David Collins}

\def\forget#1{}
%\def\qued{\hfill \vrule height 8pt width6pt depth0pt}
\def\qued{\hfill $\Box$}
\def\sep{\medskip\hrule\medskip}

\def\kk{i=n,n-1, \dots,0} 

\tolerance 10000

\begin{document} 
\vspace*{-60pt} 
\centerline{\smalltt INTEGERS: 
 \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 5 
(2005), \#G03} 
\vskip 50pt

\begin{center}
{\bf VARIATIONS ON A THEME OF EUCLID}
\vskip 20pt
{\bf David Collins}\\
{\smallit Department of Mathematics, Occidental College, Los Angeles, CA 90041, United States}\\
{\tt dcollins@oxy.edu}\\
\vskip 10pt
\end{center}
\vskip 30pt
\centerline{\smallit Received: 12/29/03, Revised: 11/5/04, 
Accepted: 4/12/05,
Published: 5/10/05}
\vskip 30pt 

\centerline{\bf Abstract}


The game of Euclid is an impartial game played between two players.
  A position in the game is a pair of integers $(a, b)$.  A move consists
of replacing the current position with one in which the larger of $a$ and
$b$ has been reduced by any multiple of the smaller.  The game ends when
the two numbers are equal.  The players alternate moves, and the winner
is the last player to make a move.  
	
Several variations take the form of restrictions on the moves 
available to the players.  One important class of restrictions takes the
form of a set $\Lambda$ of positive integers from which the number of
multiples a player removes on a turn must be chosen.

Of particular interest are versions with "dynamic" restrictions. 
 In these variations of Euclid, the maximum multiple which can be removed
on a turn is governed by some given function.  In this way, the set of
available moves changes as the game proceeds.  
	
It is shown how all versions considered can be recast
 as sequential take-away games, and this transformation is frequently
used to find winning strategies.
\normalsize

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

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\Intro{1}
\def\CF{2}
\def\SB{3}
\def\variations{4}
\def\dynamic{5}
\def\threenumber{6}
\def\miser{7}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section*{\normalsize 1. Introduction}
\label{Intro}

The game of Euclid is an impartial game played between two players.  A position in the game is a pair of integers $(a, b)$.  A move consists of replacing the current position with one in which the larger of $a$ and  $b$ has been reduced by any multiple of the smaller, with the proviso that the result must remain positive. The game ends when the two numbers are equal. Without loss of generality, we can assume that $a$ and $b$ are relatively prime and that $a\leq b$ for any position $(a, b)$. The players alternate moves, and the winner is the last player to make a move, i.e., to move to $(1,1)$.  

Euclid is a Nim-like game, and we can use 
the Sprague-Grundy theory of impartial games. 
We also employ the convention of referring to positions in which the next player to move has a win as N-positions and to those in which the previous player to move wins as P-positions (cf. \cite{WinningWays}, Ch. 4).  An N-position has a positive Sprague-Grundy value, while a P-position has a Sprague-Grundy value of zero.  

We begin our discussion of Euclid with a result which makes finding the winner 
easy.
\newtheorem{theorem}{Theorem}
\newtheorem{win}[theorem]{Theorem}
\begin{win}
The first player to have more than one available move has a winning strategy in Euclid.
\end{win}
\emph{Proof}.
If the player to move has more than one choice, we have $b>2a$.  Choose $n$ such that $a<(b-n a)<2a$.  We need to consider only two of the possible moves from $(a,b)$: to $(a,b-n a)$ and to $(a,b-(n+1)a)$.  Call these moves $A$ and $B$, respectively.  Then, if $B$ is a P-position, the first player can simply move there.  Otherwise, moving to $A$ will force the second player to move to $B$.  Clearly, the first player will
 win in one of these cases. \qued\\

There are a few interesting things about this theorem.  First, it is non-constructive: it does not actually tell us how to win.   Later on, we shall see several different ways of constructing the winning strategy.  The advantage of this form is that the principle of the first player with a choice winning applies to many variants of Euclid while the winning strategy itself varies.  Second, it applies equally well to the 
\emph{mis\`ere} form of the game where the last player to move loses.  In many Nim-like games, solving the mis\`ere version is---relative to solving the standard version---misery (a miserable pun).  Fortunately, this is not the case with Euclid, at least as far as knowing who has a winning strategy (as we shall see in Section~\miser). 
%\ref{miser}
 

The first and probably the simplest way to approach the task of finding explicit winning strategies in the game of Euclid is to use the golden ratio, $\phi$.  
We claim that in Euclid, the first player has a win in exactly those positions in which $b/a>\phi$.  The validity of this claim depends on the following two assertions:
\begin{enumerate}
\item From every position for which $b/a>\phi$, there is a move which leaves a position $(a',b')$ with 
$1\le b'/a'<\phi$.
\item Any move from a position with $b/a<\phi$ leaves a position $(a',b')$  with $b'/a'>\phi$.
\end{enumerate}
These conditions are equivalent to the assertion that the positions in Euclid with a Sprague-Grundy value of $0$ are precisely those with $1 \leq  b/a<\phi$.  The interested reader can consult \cite{Lengyel} for a proof that these conditions do indeed hold. 

I shall refer the game considered above as the standard version of Euclid. This paper shall consider many variations of these standard rules.  We shall consider first variations in which the number of multiples of $a$ which can be removed from $b$ in a position $(a,b)$ must be chosen from a fixed set $\Lambda$.  We shall present a solution for the simplest of these restriction sets, $\Lambda_{k}=\{1,2,\ldots,k\}$, and extend this theory to many other restriction sets  in Section~\variations.
%\ref{variations}.  
Theorem~\ref{theorem:Lengyel} gives a necessary and sufficient condition for which a larger restriction set is equivalent to some $\Lambda_{k}$.  We next consider 
%several 
``dynamic'' restrictions which are not fixed but rather change as the game progresses and solve Euclid for one class of such restrictions, the move size restriction,  in Theorem~\ref{theorem:David} (Section~\dynamic
%\ref{dynamic}
).  The Sprague-Grundy theory  
does not seem to be
useful in analyzing these dynamic restrictions because the winner in a given position is determined not only by the position itself but also by the preceding move. 

After a brief discussion of standard Euclid with three numbers rather than two (Section~\threenumber),
%\ref{threenumber}), 
we conclude with a discussion of {\em mis\`ere} forms.
In Section~\miser,
%\ref{miser},
Theorem~\ref{theorem:miser} 
provides the winning strategy for the mis\`ere forms of both standard Euclid and of versions with restriction sets equivalent to some $\Lambda_{k}$.

For a game $(a,b), a<b, $ we will use the continued fraction representation (Section~\CF)
%\ref{CF}) 
of $b/a$ throughout and will often view the game as played in the Stern-Brocot tree (Section~\SB).
%\ref{SB}).

\vskip 30pt 

\section*{\normalsize 2. Continued Fractions}
\label{CF}
A second method of describing the winning strategy (besides the $\phi$-based approach seen above) is through continued fractions.  This method has the advantage of being more amenable to the analysis of the various variations of Euclid which are the subject of this paper.  Each fraction $b/a$ can be represented as a continued fraction in two ways: as $[a_{0},a_{1},\ldots,a_{n}]$ (called the short form) and as $[a_{0},a_{1},\ldots,a_{n}-1,1]$.  Later on, we shall see why it does not matter which form of the continued fraction expansion we use.

It is possible to reinterpret Theorem $1$ in terms of continued fractions.  Euclid was first analyzed in this way by  Lengyel in \cite{Lengyel}. In the position $(a, b)$, $b/a=[a_{0},a_{1},\ldots,a_{n}]$, a move affects only the leading continued fraction digit $a_{0}$. If $a_{0}=1$, the player to move will have only one option.  We therefore assume that the game is played until some player has a real choice, and $a_{i}\geq 2$  with some $i$. (The existence of such $i$ is guaranteed by writing $b/a$ in the short continued fraction form.)  Since this continued fraction is certainly greater than $\phi$, that player has a winning strategy. 

\vskip 30pt 
\section*{\normalsize 3. Sequential Take-away Games}
\label{SB}
The above approach works quite well for the standard version and some of its variations \cite{Lengyel}. 
Nevertheless,  
we have found it more convenient in investigating a wide variety of generalizations to look at the game of Euclid as what 
we call a {\em sequential} take-away game.  

A simple take-away game is an impartial game played between two players.  A position consists of a single pile of counters, and the players take turns removing some positive number of counters from this pile, subject to the rules of the particular game.  The position $(1,n)$ in Euclid corresponds to an utterly trivial take-away game with a pile size of $n-1$ and no movement restriction whatsoever.  

Now that we possess the concept of a take-away game, we can define a sequential take-away game as a game which is divided into a series of smaller ``subgames'' to be played in a given order, each of which is a take-away game having the same movement restrictions.  The players alternate throughout the game; the player to move last in a given subgame moves second in the game following it (cf. \cite{Lengyel}).  Such a game is denoted by $[a_{0},a_{1},\ldots,a_{n}]$, where $a_{0}$ is the pile size in the first subgame, $a_{1}$ the pile size in the second, and so on.

The game of Euclid is a sequential take-away game, somewhat disguised.  The continued fraction representation of the position $(a,b)$ reveals the disguise.  Let $a/b$ have continued fraction expansion $[a_{0},a_{1},\ldots,a_{n}]$ (cf. \cite{Concrete}).  The players' moves reduce the size of the first coefficient $a_0$ until it is zero ($a_0$ reflects the number of multiples of $b$ which must be removed from $a$ before the result is less than $b$).  Then, the play continues from a position with continued fraction representation $[a_{1},\ldots,a_{n}]$, and with the players reducing $a_{1}$.  Thus, Euclid is a sequence of take-away games with successive pile sizes of $a_{0},a_{1},a_{2},$ and so on.  The only exception is that one must be subtracted from the last partial quotient of the continued fraction expansion of $a/b$, because $[1]$ (corresponding to the Euclid position $(1,1)$) is a terminal position and does not reflect an option.    


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  From this point on, we shall assume that one has already been removed from the last term whenever we consider a Euclid position (or any position) as $[a_{0},a_{1},\ldots,a_{n}]$.  (Therefore, the ``Euclid position representation" $[a_0, a_1, \ldots, a_n]$ for the game $(a, b)$ differs slightly from the original continued fraction expansion of $b/a$. In fact, this is why it does not matter which of the two continued fraction forms was used in the first place.) 

%%%%%%%%%%%%%
\def\k{i}
%%%%%%%%%%%%%

Looking at the game of Euclid as a sequential take-away game makes finding the Sprague-Grundy number of any position much easier; whereas without continued fractions they are rather obscured.  To find the Sprague-Grundy values, we work from right to left: to find the Sprague-Grundy value of $[a_{0},a_{1},a_{2},\ldots,a_{n}]$, we look first at the Sprague-Grundy value of $[a_{n}]$, then $[a_{n-1},a_{n}]$, and so on.  To find $g([a_{\k},\ldots,a_{n}])$, we need to know only $a_{\k}, \k<n,$ and the Sprague-Grundy value of $[a_{\k +1},a_{\k+2},\ldots,a_{n}]$.  In \cite{S-G_Euclid}, Lengyel refines the use of this method to calculate the Sprague-Grundy values for Euclid, and shows how it is related to the Stern-Brocot tree \cite{Concrete}.  Later on in this paper, we shall employ a similar recursive technique when looking at variations of Euclid. 

\section*{\normalsize 4. Static Restrictions}
\label{variations}
Many different ways of extending the game of Euclid are covered in this paper.  Probably the most natural way is to restrict the choice of multiples which can be removed to a given set $\Lambda$.  This type of restriction remains constant throughout the game and is referred to as a static restriction.  In the standard form of Euclid, the number of multiples of $a$ which are removed from $b$ is chosen from the infinite set $\Lambda=\{1,2,\ldots\}$.  We can change this set $\Lambda$ and produce any number of variations on the game.   
Lengyel \cite{Lengyel} solves Euclid for the restriction sets $\Lambda_{k}=\{1,2,\ldots,k\}$. These games are the sequential extensions of Bachet's subtraction game, a single-pile take-away game where only $1, 2, \dots, k$ counters can be removed on a turn. (In general, a subtraction game consists of the players removing some number of counters from a single pile where the number removed must be chosen from a restriction set \cite{WinningWays}, Ch. 4.)  The Sprague-Grundy function of Bachet's game has the period $(0,1,\dots,k)$ of length $k+1$.  

Many subtraction-based games with finite or infinite restriction sets display a similar periodicity and are equivalent to Bachet's game for some $k$. For example, the single-pile take-away game with restriction set $\{1,2,3,5,\ldots,p_{k},\ldots\}$, with $p_k$ being the $k$th prime number,  has the same Sprague-Grundy function as Bachet's subtraction game with $\Lambda_3=\{1,2,3\}$.  Now, we show that games which are equivalent to one of Bachet's games in the one-pile version are equivalent in Euclid as well.  More formally, let $G$ be any static restriction game and let $B_{k}$ be Bachet's subtraction game with the set $\{1,2,\ldots,k\}$ of allowed subtractions. We denote the Sprague-Grundy functions of $G$ and $B_{k}$ by $g_{G}$ and ${g_{B}}_{k}$, respectively. We write $G \equiv_{c} B_{k}$ if games $G$ and $B_{k}$ have the same Sprague-Grundy function with $c$ $(c \leq k)$ being the Sprague-Grundy value of the terminal position, i.e., $g_{G}={g_{B}}_{k}$ and $g_{G}(0)={g_{b}}_{k}(0)=c$. 

 If $G$ and $B_{k}$ have the same Sprague-Grundy function for all $c \leq k$, we write $G \equiv B_{k}$.  In the one-pile form, of course, the value of the terminal position is zero; but as we have seen above, a Euclid position $[a_{0},a_{1},\ldots,a_{n}]$ is equivalent to the one-pile game with $a_{0}$ counters, the only difference being that the Sprague-Grundy value of the terminal position is $g([a_{1},a_{2},\ldots,a_{n}])$ rather than zero.  The following theorem was suggested by Lengyel.

\newtheorem{Lengyel}[theorem]{Theorem}
\begin{Lengyel}
\label{theorem:Lengyel}
$G \equiv_{0} B_{k}$ if and only if $G \equiv B_{k}$.
\end{Lengyel}
%
\emph{Proof}.  
The ``if" part of the statement is obvious. For the other part we need
%
\\

\noindent{\bf {Lemma.}}
%\begin{lemma} 
If $G\equiv_0 B_k$ then $\Lambda_{G} \supseteq \Lambda_{k}$ for the subtraction set $\Lambda_{G}$ of game $G$.
%\end{lemma}  
\\

\noindent{\em Proof of the lemma}. We proceed by contradiction. Suppose that $\Lambda_{G} \not\supseteq \Lambda_{k}$.  Let $m$ be least element of the difference set $\Lambda_{k}\setminus \Lambda_{G}$. We have $1 \leq m \leq k$. Then clearly, $g_G(m)=0$
because we can only move to $1, 2, \dots, m-1$  in $G$, and they have non-zero values, for $g_G(i)=g_{B_k}(i)=i,  0\le i\le k$, by $G\equiv_0 B_k$. On the other hand, $g_{B_k}(m)\not=0$
because we can move to zero in $B_k$.  Thus, $G \not \equiv_{0} B_{k}$, a contradiction. \qued\\

Assume that $\Lambda_{G} \setminus \Lambda_{k} \not= \emptyset$.  Now, let $s$ be any element of $\Lambda_{G} \setminus \Lambda_{k}$, thus  $s>k$ by the lemma.  There are two cases.  
\begin{enumerate}
\item For all $s \in \Lambda_G\setminus \Lambda_k$ there exists an $s' \in \Lambda_{k}$ such that $s-s' \equiv 0 \bmod (k+1)$.  We now prove by contradiction that $G\equiv B_k$.  (In this case, the option $s$ really adds nothing to the options to remove $1,\ldots,k$, and does not affect the Sprague-Grundy function.)  By the lemma, $\Lambda_{G} \supseteq \Lambda_{k}$, so that $g_{G}(i)=g_{B_k}(i)$ for all $i \leq k$. Now let $t$ be the least element for which $g_{G}(t)\not=g_{B_k}(t)$.  Then $t > k$ and
%%%%%%%%%
\[
g_{G}(t)=
mex\left\{
\left
\{
{\bigcup_{i=1}^{k} g_{G}(t-i)}
\right\} 
\bigcup
\left\{
\bigcup_{{s \in \Lambda_{G} \setminus \Lambda_{k}}\atop {s\leq t}} g_{G}(t-s)
\right\}
\right
\}=\]
%%%%%%%%%%
\[=mex\left\{\bigcup_{i=1}^{k} g_{B_{k}}(t-i)\right\}=g_{B_{k}}(t).
\]
%%%%%%%%%%%%%%
%%%%%%%%%
 The second step in this equality is justified since  $g_G(t-s)=g_{B_{k}}(t-s)=g_{B_{k}}(t-s')$ where $s' \in \Lambda_{k}$ and $s \equiv s' \bmod(k+1)$ by the hypothesis.  We have a contradiction.  

\item There exists an $s\in \Lambda_G\setminus \Lambda_{k}$ such that for all $s'\in \Lambda_{k}$, 
we have $s-s' \not\equiv 0 \bmod (k+1)$, i.e., $g_{B_k}(s-s')\not=0$.    In the games $G$ and $B_{k}$, both with $g(0)=0$, we consider the value of $g(s)$.  We know that $g_{B_{k}}(s)=0$, otherwise there would exist an option to move to $s-s'$ in $B_{k}$  with $s-s' \equiv 0 \bmod (k+1)$, violating our assumption. On the other hand, $g_{G}(s) \not= 0$, because $g_{G}(s-s)=g_{G}(0)=0$.  This contradiction shows that $G \not \equiv_{0} B_{k}$, so this case never occurs under the hypothesis of the theorem.
\qued
%\\
\end{enumerate}
%\qued\\
%
{\em Remark}. If indeed $G$ is equivalent to any $B_{k}$, the value of $k+1$ will be the least integer not in $\Lambda_{G}$.  In fact, it is not too difficult to see that $G \equiv B_{k}$ if and only if $\Lambda_{G}$ contains $\{1,\ldots,k\}$ but no multiples of $k+1$.\\
%

\noindent
This theorem and the remark allow us to apply the theory of Euclid with restriction set $\Lambda_{k}=\{1,2,\ldots,k\}$ to Euclid with other restriction sets.  We summarize this 
approach here.  In the position $[a_{0},a_{1},\ldots,a_{n}]$, each of the partial quotients can be reduced $\bmod (k+1)$.  Then, the game plays exactly as in the unrestricted Euclid, except that it may take somewhat longer.  In particular, the first player facing a position with $a_{i}\geq 2$ has a winning strategy.  This extends our first theorem to the restriction sets $\Lambda_{k}$ and restrictions equivalent to these 
by the above theorem.  We now turn to some examples of infinite sets which are equivalent to $\Lambda_{k}$.\\  
\\
\emph{Example~1}: $\Lambda=\{1$ and any number of odd numbers$\}$.\\
\\
Since one is present but all multiples of two are excluded, this game is equivalent to $B_{1}$, a completely deterministic game.  In this variation of Euclid, there is never a ``real" choice (for the parity of the number of remaining moves changes by every move \cite{Lengyel}), and the result is completely unaffected by skill. \\
 \\
\emph{Example~2}: $\Lambda=\{1,2,\ldots,2^n,\ldots\}$.\\
\\
Since the multiples of three are not powers of two, 
it is now clear that the version of Euclid with $\Lambda=\{1,2,\ldots,2^n,\ldots\}$ is completely equivalent to $B_{2}$.
At any point, we need only use the options $\Lambda_2=\{1,2\}$ to reduce any non-zero position to zero.  The additional options serve only to shorten the game as in example 1.\\ 
\\
\emph{Example~3}: $\Lambda=\{1,2,3,5,\ldots,p_{k},\ldots\}$.\\
\\
The set of primes works in an analogous way.  This variation of Euclid reduces to $B_{3}$.  Again, since multiples of four are not prime, the multiples of four are the positions with Sprague-Grundy value of zero.  In any position, we need only to use the removal options $\Lambda_3=\{1,2,3\}$. \\
\\
\emph{Example~4}: $\Lambda=\{p^k$ for all primes $p, k=0,1, \dots\}$.\\
\\
We leave it to the reader to show that the removal set of prime powers is equivalent to $\Lambda_{5}$.


\vskip 30pt 
\section*{\normalsize 5. Dynamic Euclid}
\label{dynamic}
%
We next consider ``dynamic'' versions of Euclid in which the maximum multiple which can be removed on a given turn is governed by the game function, $f$.  In this way, the set of available moves dynamically changes as the game proceeds.  Typically, the reduction technique of Section~\variations\
%\ref{variations} 
cannot be applied when dynamic restrictions are imposed on the available moves. In one class of dynamic games, the maximum number of counters $f(n)$ which can be removed is a function of the pile size $n$.  In \cite{Pilesize}, Holshouser, Reiter, and Rudzinski show how to calculate the Sprague-Grundy values $g(n)$ given a game function $f(n)$. We note that Theorem~1 of \cite{Pilesize} guarantees that many of these games cannot be equivalent to $\Lambda_k$ for any $k$.

  In its Euclid form the pile size restriction makes the maximum number of multiples of $a$ which can be removed from $b$ in $(a,b)$ a function of the maximum number which could be removed were there no restriction.   The Sprague-Grundy numbers of each position in a pile size restriction can be found recursively using the representation of Euclid as a sequential take-away game introduced earlier and working from right to left.  Suppose that a Euclid position $(a,b)$ has the representation $[a_{0},a_{1},\ldots,a_{n-1},a_{n}]$  Then, the last segment $[a_{n}]$ is a single-pile take-away game with pile size $a_{n}$, so $g([a_{n}])$ can be found using the theory of \cite{Pilesize}. Then, the Sprague-Grundy function $g([a_{n-1},a_{n}])$ is clearly just $g([a_{n-1}])$ permuted so that the output $0$ is replaced by $g([a_{n}])$ and the values less than or equal to $g([a_{n}])$ are shifted down by one, or, more formally,
\[
g([a_{n-1},a_{n}])=
\begin{cases}
g([a_{n-1}])-1, &\text{if } g([a_{n-1}]) \leq g([a_{n}]) \text{ and } g([a_{n-1}])\neq 0,\\
g([a_{n-1}]), &\text{if } g([a_{n-1}]) > g([a_{n}]), \\
g([a_{n}]), &\text{if } g([a_{n-1}])=0.\\
\end{cases}
\]
Similarly, we can now find $g([a_{n-2},a_{n-1},a_{n}])$ as a function of $g([a_{n-2}])$ and $g([a_{n-1},a_{n}])$, and continue recursively in this fashion until the Sprague-Grundy value of the entire game is known.  Thus, we see how results of \cite{Pilesize} extend directly to Euclid.   \\

Another class of dynamic take-away games makes the maximum number of counters which can be removed on a given turn a function of the previous move.  The theory of one-pile games with this {\it move size} restriction has been solved by Schwenk in \cite{Schwenk}.  Here, we offer a complete extension of his theory to the game of Euclid.  It will be noted that in Euclid, the restriction is on the maximum number of multiples of $a$ which can be removed from $b$ in a position $(a,b)$, $b\geq a$; and this restriction is a function of the number of multiples removed on the previous turn.  Games with a move size restriction are especially difficult to handle because the characterization of the Sprague-Grundy numbers is problematic and does not immediately give the winner and winning strategy.  This is why Schwenk chooses a different approach.

Space prevents us from giving all the details of Schwenk's theory here; the interested reader should consult 
\cite{Schwenk}.  What follows is a brief summary. 
%
In a take-away game, let the maximum number of counters to be removed on the $k$th  ($k\ge 2)$ move be $f(T(k-1))$, where $T(k-1)$ is the number removed on the previous move and $f$ is a non-decreasing function. (Also, we exclude the possibility of removing all counters on the first move in the one-pile version.) 

For example, we might have a game in which one can remove only up to twice as many counters as were removed on the previous move; in this case $f(n)=2n$ (cf. \cite{Schwenk} and \cite{Knuth}, Section 1.2.8, \#37). The idea of Schwenk's theory is to define a sequence $H_{i}$ such that $H_{1}=1$ and $H_{k+1}=H_k+H_{j}$, where $j$ is the smallest index such that $f(H_{j}) \geq H_k$.  In our example, $H_{1}=1$, $H_{2}=H_{1}+H_{1}=2$, $H_{3}=H_{2}+H_{1}=3$, and it is not too difficult to see that in general $H_{k+1}=H_{k}+H_{k-1}$.  Thus, the sequence $H_{i}$ is the Fibonacci sequence in our case.  


\def\n{m}


Schwenk demonstrates that each number $N$ is represented uniquely by a sum of $H_{i}$s, where $N={H_{j}}_{1}+{H_{j}}_{2}+\cdots+{H_{j}}_{\n}, j_1<j_2\dots<j_\n$, and $f({H_{j}}_{i})<{H_{j}}_{i+1}$.  In our example, this statement becomes {\em Zeckendorf's Theorem}, which states that each number is represented uniquely as a sum of non-consecutive Fibonacci numbers. The number of elements in this sum is the \emph{norm} $|N|$ of $N$. Clearly, $|N|=0$ if and only if $N=0.$ In \cite{Schwenk}, Schwenk proves\\ 

%\newtheorem{norm}{Theorem}
%\begin{norm} 
\noindent{\bf Theorem~A } The first player to be able to reduce the norm has a winning strategy.  The only winning strategy is to reduce the norm. \\
%\end{norm}
%
%\noindent

Schwenk's idea is to make up $N$ as a sum of ``losing" positions, $H_j$s. In fact, each $H_j$ as a starting position is a P-position of norm one which cannot be decreased on the first move.
%%%
If a player can reduce $N=H_{j_1}+\dots+H_{j_\n}$ with $ j_1<j_2\dots<j_\n$ and  $|N|=\n\ge 2,$ by removing $H_{j_1}$ then the other player cannot immediately remove $H_{j_2}$, for $f(H_{j_1})<H_{j_2}$. Therefore, any legal removal by the other player will not decrease the norm.
Also note that all winning 
removals can be characterized as partial sums of
$H_{j_1}+H_{j_2}+\dots+H_{j_\n}$ (cf. 
\cite{Knuth}).


To extend the Schwenk theory to Euclid, we need to employ a new function.  Define $h(N), N=H_{j_1}+\dots+H_{j_\n}$,  as the least $H_{i}$ such that $f(H_{i})\geq H_{j_1}=H_{j_1}(N)$. 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The definition implies that $|h(a)|=1, f(h(a))\ge H_{j_1}(a),$ and if $H_i<h(a)$ then $f(H_i)< H_{j_1}(a)$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\sep
\\

We now consider the Euclid position $[a_{0},a_{1},\ldots,a_{n}]$. If $n=0$
 then we are back to the one-pile version covered by Theorem~A \cite{Schwenk}.
We now have the following theorem:
\newtheorem{Schwenk}[theorem]{Theorem} 
\begin{Schwenk}\label{theorem:David}
%\hspace*{20pt}
Assume that $n \ge 1$.
% 
\begin{enumerate}
\smallskip
\item [{(1)}] The position $[a_{0},a_{1},a_{2},\ldots,a_{n-1},a_{n}]$ has the same winner as the first position in the series $[a_{0},\ldots,a_{n-1}-h(a_{n})]$, $[a_{0},\ldots,a_{n-2}-h(a_{n-1})]$, \ldots, $[a_{0},\ldots,a_{i}-h(a_{i+1})]$,\ldots, $[a_{0}-h(a_{1})]$ in which the last 
%
partial quotient $a_{i}-h(a_{i+1})$ is non-negative.  
\item [{(2)}] If $a_{i}-h(a_{i+1})<0$ for $i=0,1,\ldots,n-1$, the first player is always the winner.
\end{enumerate}
Any position can be reduced to a shorter position (i.e., one with fewer terms in the Euclid position representation) with the same winner in one of these two ways.  By recursively applying these reductions, we eventually reach a one-pile position whose winner is known by Schwenk's theory.
\end{Schwenk}
\emph{Proof}.
We first prove the second assertion of the theorem.  Suppose that in $[a_{0},a_{1},\ldots,a_{n}]$, $a_{i}-h(a_{i+1}), i=0,1, \dots, n-1,$ is always negative.  Then the first player 
%
can win by adopting the strategy of reducing the norm 
of $a_0$
by {\em one} on each move.  In this way, that player will eventually reduce $a_{0}$ to zero by removing some $H_{i}$ satisfying $H_{i}\le a_{0}<h(a_1)$.  We have $f(H_{i})<H_{j_1}(a_{1})$ by definition, so that even the smallest norm-reducing removal is precluded and the next player will be unable to reduce the norm of $a_{1}$.  Therefore, the first player will be able to apply the same strategy of reducing the norm by one.  It is clear that the first player will win each subgame in this fashion and thus the entire game.  

We can now prove the first part of the theorem.  Assume that $a_{i}$ is the greatest index such that $a_{i}-h(a_{i+1})$ is non-negative.  Then, the winner of $[a_{0},a_{1}, \ldots, a_{i}-h(a_{i+1})]$, say Player A, will be able to reach the position $[h(a_{i+1}),a_{i+1},\ldots,a_{n}]$. We must show that this is a P-position.  Clearly, $h(a_{i+1})$ has norm one, so the only way for  Player B to reduce it is to eliminate it entirely.  This, however, allows Player A to reduce the norm of $a_{i+1}$ by removing $H_{j_1}(a_{i+1})$, by the definition of $h(a_{i+1})$ (for $f(h(a_{i+1}))\geq H_{j_1}(a_{i+1})$).  In this case, (2) shows that Player A wins, since each $a_{l}-h(a_{l+1}), l\ge i+1,$ is now negative.  If, on the other hand, Player B does not reduce the norm of $h(a_{i+1})$ but instead moves to $[k,a_{i+1},\ldots,a_{n}]$, then Player A can win by adopting the strategy of reducing the norm of $k$ by one on each turn (cf. Theorem~A guarantees that Player B, by missing the opportunity to decrease the norm, allows Player A to do so).  In this way, Player A eventually will be the one to move to $[a_{i+1},\ldots,a_{n}]$.  However, Player A will reach this position by removing some $H_{j}<h(a_{i+1})$ (recall that Player B faced $[h(a_{i+1}),a_{i+1},\ldots,a_{n}]$).  Thus, again by the definition of $h(a_{i+1})$ (for $f(H_j)<H_{j_1}(a_{i+1})\le a_{i+1}$), Player B will be unable to reduce the norm of $a_{i+1}$ and loses by (2). \qued\\
\\
%
\emph {Example~1. } In all of the following examples assume that the move function is $f(n)=2n$. Consider the position $(25,87)$, i.e., $[3,2,11]$.  This reduces to $[3,2-h(11)]=[3]$ by (1).  Thus, the first player can win by moving to the P-position $[2,11]$, i.e., $(12,25)$, first.  How the first player wins from here by playing second is not directly given by Theorem~\ref{theorem:David} but is outlined in its proof. If the second player moves to $(1, 12)=[11]$, the first player can reduce the norm of $11=3+8$ by moving to $[8]$.  If the second player instead moves to $[1,11]=(12, 13)$, the first player moves to $[11]=(1,12)$. Then, the second player can remove one at most twice and is unable to reduce the norm.  Thus, the first player wins in all cases, as Theorem~\ref{theorem:David} claims.  \\
\\
%
\emph {Example~2. } Now consider the position $[1,5,11]$.  This reduces to $[1,5-h(11)]=[1,3]$ by (1).  Now, since $1-h(3)=-1$, we use (2) and reduce to $[1]$.  Thus, the first player wins by removing $1$ and moving to $[5,11]$. Now, any response allows the first player to reach the P-position $[2,11]$ and win as above.   \\
\\
%
\emph {Example~3. } Finally, consider the position $[2,3,13]$.  We first try $[2,3-h(13)]$, but because $3-h(13)=-5$ is negative, we instead reduce to $[2-h(3)]=[0]$.  Thus, this is a P-position and a loss for the first player.  The reader can check all the variations.  

\vskip 30pt 
\section*{\normalsize 6. The Euclid of Three Numbers}
\label{threenumber}


Consider an extension of Euclid in which a position is $(a,b,c)$, where $a,b,c$ are integers.  There are many ways to generalize the rules of standard Euclid.  Suppose we decree that a legal move is to remove the same multiple of the smallest integer from each of the larger two.  Then it is not hard to see that the idea of Theorem~1 applies.  

Assume without loss of generality that in $(a,b,c)$ we have $a \leq b \leq c$.  Then, assuming that $b>2a$, we choose $n$ such that $a<b-n a<2a$.  Then one of the moves $(a,b-n a,c-n a)$ or $(a, b-(n+1)a,c-(n+1)a)$ will win, for if the latter does not, the first player can take the former and force his opponent to move there.

The reader may object that this is hardly the most natural way of generalizing Euclid to three numbers, and the author sympathizes.  To me, the most natural extension would be to make a legal move the decreasing of any of the three integers by a multiple of any other, provided the result remains positive.  Unfortunately, I have not been able to find any winning strategies in this variation of Euclid, and doing this remains the most intriguing unsolved problem in the domain.  The general theme that a player with many options has a winning strategy seems to hold, but there are some surprising P-positions; for example, $(4,9,16)$.

\vskip 30pt 
\section*{\normalsize 7. Mis\`ere forms}
\label{miser}
%
As we mentioned in Section~\Intro,
%\ref{Intro}, 
the mis\`ere form of Euclid is a win for the first player with a choice of moves.  Our next theorem gives a winning strategy.
% 
\newtheorem{Misere}[theorem]{Theorem}
\begin{Misere}
\label{theorem:miser}
The first player to have a choice can win mis\`ere Euclid 
%
by adopting the following strategy: when faced with the position $[a_{i},a_{i+1},\ldots,a_{n}]$, with $a_{i}\geq2$, make the same move as in the 
unrestricted
version if at least one of $a_{i+1},\ldots,a_{n} \geq 2$.  Otherwise, play so as to leave an odd number of ones (whereas in  
unrestricted
version one would leave an even number).
This strategy works for Euclid with no restriction, restriction sets $\Lambda_k$, and other equivalent restriction sets.
\end{Misere}
%
\emph{Proof}.  If at least one of $a_{i+1},\ldots,a_{n} \geq 2$, playing as in the 
unrestricted
 version will ensure that the first player will make the next choice.  Thus, the position will be reduced to a smaller one in which the first player still has control.  If $a_{i+1}=a_{i+2}=\cdots=a_{n}=1$, there are no more choices.  In this case, playing to leave an odd number of ones will ensure that the second player's moves always leave an even number, eventually making the last move by leaving zero, and giving the first player victory.  Note that it is always possible for the first player to leave an odd number, because $[1,a_{i+1},\ldots,a_{n}]$ and $[a_{i+1},\ldots,a_{n}]$ are two options.  This completes the proof for the 
unrestricted
version.  
%
This strategy also applies to the mis\`ere games 
% 
with restriction set $\Lambda_{k}$ and  
other equivalent restriction sets (in the sense described in Section 4).  All we need 
to
do is to reduce all the partial quotients $\bmod (k+1)$ and apply the above strategy.  \qued

\vskip 30pt 
\section*{\normalsize Acknowledgments}
The author wishes to thank Occidental College and, in particular, the Undergraduate Research Center for approving this research and providing funding.  He especially wishes to thank his faculty mentor Tam\'{a}s Lengyel for many suggestions and careful reading of this paper as well as for suggesting this research topic.  He also thanks the referee for helpful suggestions which improved the presentation of the paper.
%  
\vskip 30pt 
%\section*{\normalsize {References}}
\renewcommand\refname{\normalsize {References}}
\begin{thebibliography}{9} \footnotesize
\bibitem{WinningWays} Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy.  {\em Winning Ways for Your Mathematical Plays}.  London, New York: Academic Press, 1982.  
\bibitem{Conway} John H. Conway.  {\em On Numbers and Games}.  London, New York, San Francisco: Academic Press, 1976.
%\bibitem{Ferguson} Thomas S. Ferguson.  {\em Game Theory},  at  {\tt http://www.math.ucla.edu} /\~{\tt tom/Game}\_{\tt Theory/comb.pdf}, 2000
\bibitem{Concrete} Ronald L. Graham, Donald E. Knuth, and Oren Patashnik.  {\em Concrete Mathematics}.  Second edition. Reading, Massachusetts: Addison-Wesley Publishing Company, 1994.
\bibitem{Pilesize} Arthur Holshouser, Harold Reiter, and James Rudzinski.  {\em Pilesize Dynamic One-Pile Nim and Beatty's Theorem}.
Integers, Electronic Journal of Combinatorial Number Theory  {\bf 4}(2004), \#G03, 1--13.
\bibitem{Knuth} Donald E. Knuth. {\em The Art of Computer Programming}, vol. 1: Fundamental Algorithms, Third Edition, Reading, Massachusetts: Addison-Wesley Publishing Company, 1997.
\bibitem{Lengyel} Tam\'{a}s Lengyel.  {\em A Nim-Type Game and Continued Fractions}. Fibonacci Quarterly {\bf 41}(2003), 310--320.
\bibitem{S-G_Euclid} Tam\'{a}s Lengyel.  {\em On calculating the Sprague-Grundy function for the game Euclid}.  To appear in the 11th International Conference on Fibonacci Numbers and Its Applications, 2004.
\bibitem{Schwenk} Allen J. Schwenk.  {\em Take-Away Games}.  Fibonacci Quarterly {\bf 8}(1970), 225--234.
\bibitem{Zieve}  Michael Zieve.  {\em Take-Away Games}. Games of No Chance, MSRI Publications, vol. 29, 1996.  

\end{thebibliography}
\end{document}