\documentclass[12pt]{article}
\usepackage{latexsym}
\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


\setlength{\parindent}{0in}
\setlength{\parskip}{5pt}

\newtheorem{lemma}{Lemma}

%All of the following will be sequentially numbered

\newtheorem{definition}{Definition}
\newtheorem{theorem}[definition]{Theorem}
\newtheorem{conjecture}[definition]{Conjecture}
\newtheorem{proposition}[definition]{Proposition}
\newtheorem{cor}[definition]{Corollary}
\newtheorem{problem}[definition]{Problem}
\newtheorem{observation}[definition]{Observation}
\newtheorem{claim}[definition]{Claim}
\newtheorem{example}{Example}

\newenvironment{proof}{\noindent{\it Proof.}}{\hfill $\Box$}


\begin{document}
\begin{center}
{\bf GEOGRAPHY PLAYED ON AN N-CYCLE TIMES A 4-CYCLE}
\vskip 20pt
{\bf M. S. Hogan\footnote{The author was partially supported by an NSERC
Undergraduate Summer Research Award.}}\\
{\smallit Department of Mathematics and Computer Science,
University of Prince Edward Island,
Charlottetown, PE C1A 4P3, Canada}\\
\vskip 10pt
{\bf D. G. Horrocks\footnote{The author was partially supported by NSERC.}}\\
{\smallit Department of Mathematics and Computer Science,
University of Prince Edward Island,
Charlottetown, PE C1A 4P3, Canada}\\
{\tt dhorrocks@upei.ca}\\
\end{center}
\vskip 30pt
\centerline{\smallit Received:12/3/02, Accepted: 4/29/03, Published:
4/30/03}
\vskip 30pt

\centerline{\bf Abstract}

In the game of Geography, two players alternate moving
a coin along the edges of a directed graph.
The coin may not be moved to the same vertex more than once,
and the last player who is able to move wins.
We analyze this game played on the cartesian product
of cycles
$C_n \times C_4$.


\noindent

\pagestyle{myheadings}
\markright{\smalltt INTEGERS: 
\smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 3
(2003), \#G02\hfill}
\thispagestyle{empty}
\baselineskip=15pt
\vskip 30pt

\section*{\normalsize 1. Introduction}


{\it Geography}, as described in \cite{fraenk1} and
\cite{fraenk2}, is a game for two players, played on a directed
graph. A coin is initially placed on a vertex and, on his turn, a
player moves the coin along a directed edge to an adjacent
previously unoccupied vertex.  The players move alternately and,
under normal play, the last player who is able to move wins.

Some particular cases of Geography have been studied. For example,
{\it Kotzig's (or Modular) Nim} is played on a directed graph with
vertex set $\{ 0, 1, 2, \ldots, n-1 \}$. There is a directed edge
from $x$ to $y$ if and only if $y-x \pmod{n}$ is contained in a
given set of integers, called the {\it move set}. Many instances
of this game have been solved; we refer the reader to
\cite{berlekamp} and \cite{fraenk3} for the results.

We will assume that the reader is familiar with standard
terminology of combinatorial game theory, as described in
\cite{berlekamp}.  In particular, for an impartial game $G$,
the {\it outcome class} of $G$,
denoted ${\cal G} (G)$,
is $\cal P$ if the previous player has
a winning strategy, and $\cal N$ if the next player wins. We will
refer to our two players as Alice and Bob, with Alice playing
first.

We now define the graphs to be considered here. Let $C_n$ denote
the directed cycle with vertex set $V(C_n) = \{ 0, 1, \ldots, n-1
\}$ and edge set $E(C_n) = \{ (0,1), (1,2), \ldots, (n-2,n-1),
(n-1,0) \}$ where $(x,y)$ denotes an edge directed from $x$ to $y$.
The {\it cartesian product} $C_m \times C_n$ has
vertex set $V(C_m) \times V(C_n)$ and there is a directed edge
from $(a,b)$ to $(c,d)$ if and only if $a=c$ and $(b,d)$ is a
directed edge in $C_n$, or $b=d$ and $(a,c)$ is a directed edge
in $C_m$.

Nowakowski and Poole \cite{nowpoole} investigated the
game of Geography played on a cartesian product of two directed
cycles.
In particular, the following theorem may be found in
\cite{nowpoole}.

\begin{theorem}
\label{evencase}
If $n=2$, or if both $n$ and $m$ are even, then
${\cal G} (C_n \times C_m) = {\cal N}$.
\end{theorem}

Furthermore, the main result of \cite{nowpoole} is the
determination of the outcome class of $C_n \times C_3$ for all
positive integers $n$.

\vskip 30pt

\section*{\normalsize 2. Geography played on $C_n \times C_4$}

In this paper, we consider the game of Geography played
on $C_n \times C_4$.
The following is an immediate consequence of
Theorem~\ref{evencase}.

\begin{theorem}
If $n$ is even then
${\cal G} (C_n \times C_4) = {\cal N}$.
\end{theorem}

Therefore, we need only consider the case in which
$n$ is odd and in the sequel we will assume that this
is the case.
The rest of this paper is devoted to proving the
following result.

\begin{theorem}
\label{main}
If $n$ is an odd positive integer then
$$
{\cal G} (C_n \times C_4) =
\left\{
\begin{array}{ll}
{\cal P} & \mbox{if $n \equiv 11 \pmod{12}$}, \\
{\cal N} & \mbox{otherwise.}
\end{array}
\right.
$$
\end{theorem}

We will visualize the graph $C_n \times C_4$ as a rectangular board
having 4 rows and $n$ columns. The rows are numbered $0, 1, 2, 3$
from top to bottom and the columns are numbered $0, 1, 2, \ldots,
n-1$ from left to right: the ordered pair $(c, r)$ refers to the
cell at column $c$ and row $r$. We will assume, without loss of
generality, that the coin is initially placed at $(0,0)$ and will
denote this on the diagrams by $X$. A legal move is to move right
(in the first coordinate) or down (in the second coordinate),
including ``wrap around'' moves. Every time play reaches the last
column, we will say that one {\it pass} has occurred. We will
denote the players' moves by $A$ and $B$ for Alice and Bob,
respectively. It will be convenient, on occasion, to refer to the
$ith$ move by player Y; this will be done using the notation
$Y_i$. Further, a move that is forced upon player Y will be
denoted $Y !$ and parentheses will be used when it does not matter
which of the two available moves is played.

The cell $(c, r)$ is called a {\it sink} if it has not yet been
occupied but its followers, $(c+1, r)$ and $(c, r+1)$, have both
been played. Thus a player who is able to reach a sink wins the
game. An important notion, introduced in \cite{nowpoole}, is that
of a {\it closing-off sequence}. In the game $C_n \times C_4$,
such a sequence of moves has one of the following forms.

$
\begin{array}{ccccccccccc}
S_1 & = & (a,i) &
\rightarrow & (a+1,i) &
\rightarrow & (a+1,i+1) &
\rightarrow & (a+1,i+2) &
\rightarrow & (a+1,i+3)
\\
S_2 & = & (a,i) & \rightarrow &
(a,i+1) & \rightarrow &
(a+1,i+1) & \rightarrow &
(a+1,i+2) & \rightarrow &
(a+1,i+3)
\\
S_3 & = & (a,i) &
\rightarrow & (a,i+1) &
\rightarrow & (a,i+2) &
\rightarrow & (a+1,i+2) &
\rightarrow & (a+1,i+3)
\\
\end{array}
$

Notice that a closing-off sequence creates a sink at $(a,i+3)$
(assuming that it has not yet been occupied) and that the game
will end no later than at this cell on the next pass. As we will
see in the next section, a player who is the first to complete a
closing-off sequence on the first pass wins the game.

\vskip 30pt

\section*{\normalsize 3. Preliminary Lemmas}

In this section, we establish two lemmas,
namely Lemma~\ref{closing} and Lemma~\ref{sink},
which present
conditions under which one player may force a win.
They will be used repeatedly in the proof of
Theorem~\ref{main}.

\begin{lemma}
\label{colone}
If the first two moves of the game are in the first column
then Alice has a winning strategy.
\end{lemma}

\begin{proof}
We have that Alice's first move is to $(0,1)$ and Bob
replies to $(0,2)$.
Suppose now that Alice moves to $(0,3)$:
Bob is then forced to respond with $(1, 3)$.

Alice's winning strategy now is to always play down.
Note that this move is always available to her and that
Bob is always the first player to reach a new column.
Eventually then, Bob will be the first to play on the last
column and, as the game cannot wrap around to the first column,
Alice will win.
\end{proof}

Therefore, should Alice begin the game by moving down to $(0,1)$,
Bob is forced to respond by moving across to $(1,1)$.
In the sequel then, we will assume that, on the first pass,
neither $(0,2)$ nor $(0,3)$ are occupied.

\begin{lemma}
\label{closing}
A player who completes a closing-off sequence on the first pass,
and is the first to do so, has a winning strategy.
\end{lemma}

\begin{proof}
Suppose that Alice is the first player to complete a
closing-off sequence and does so on the first pass by moving to
$(a+1,i)$.
This move creates a sink at $(a,i)$ and we show that Alice
wins the game by moving to this vertex on the second pass.

First, notice that since $n$ is odd,
colouring the vertices in a checkerboard fashion shows that
Alice will be the player to reach $(a,i)$ on the second pass.

Second, it must be shown that the game will not end before
Alice reaches $(a,i)$.
We observe that, since the game cannot proceed beyond column $a$
on the second pass,
it will end earlier if and only if another sink is both created and
occupied {\it on the same pass}.
In order for this to happen, the players must make four
consecutive moves (two moves each) in the same column.
We claim that this cannot happen if Alice always moves across
when it is possible to do so.

Clearly, up to the second last column of the first pass, Alice can
always move across.
At the last column, however, Alice may be forced to move down once
(if Bob has played to $(n-1, 0)$, for example).
However, play will not ``go around'' in the second coordinate
in the last column because in order for this to happen,
Bob must move to either $(n-1, 2)$ or $(n-1, 3)$.
In either case, since we assume that neither $(0,2)$ nor $(0,3)$
are occupied on the first pass, the across move will be available
to Alice.
Finally, once the second pass has begun, it is impossible for
play to go around in any one column since each column contains
at least one occupied cell.
Therefore, regardless of how the players move, play must continue
until Alice reaches the sink at $(a,i)$ and wins.
\end{proof}

\begin{lemma}
\label{sink}
If the last two moves on the first pass are to
$(n-2,1)$ and $(n-1,1)$ then Alice wins.
\end{lemma}

\begin{proof}
Colouring the cells in a checkerboard fashion,
we see that, since $n$ is odd, Bob must be the
player to move to $(n-2,1)$ and it is Alice's
response to $(n-1,1)$.
Thus a sink is created at $(n-1,0)$.
Bob's response will be to either $(n-1, 2)$
or $(0,1)$.
In either event, Alice's winning strategy is to
reply to $(0,2)$ which, by the assumption following
Lemma~\ref{colone}, will be unoccupied.

As in the proof of Lemma~\ref{closing},
once the second pass has begun, it is impossible for
play to go around in any one column since each column contains
at least one occupied cell.
Therefore, play will eventually reach the second last column
and the first player to do so
will be Alice at $(n-2, 3)$, or Bob at $(n-2, 0)$ or
$(n-2, 2)$.
If Alice moves to $(n-2, 3)$ then Bob's next move is to either
$(n-1, 3)$ or $(n-2, 0)$.
In either event, Alice may reply to $(n-1, 0)$ and win.
If Bob moves to $(n-2, 2)$ then Alice replies to $(n-2, 3)$ and
has a winning strategy as described above.
Finally, should Bob move to $(n-2, 0)$ then Alice replies to
$(n-1, 0)$ and wins.
\end{proof}


\vskip 30pt

\section*{\normalsize 4. Two Special Move Sequences}

\subsection*{\normalsize 4.1 Playing the 12}

Our analysis of the game $C_n \times C_4$ will depend upon
the value of $n$ modulo 12.
The underlying reason for this is that, on the first pass,
a player may force his opponent into repeating a block of moves
comprising 12 columns.
We call this {\it playing the {\bf 12}}.

Let us suppose that, on the first pass, Bob is the first player to
reach column $c$ and does so by playing to $(c,0)$, denoted by
$B_0$ on the diagram below.
Alice may
then dictate the play for the next 12 columns so that Bob will be
forced to be the first player to reach the $(c + 12)th$ column by
playing to $(c + 12, 0)$.  The following diagram describes Alice's
strategy.  Recall that ! indicates a forced move and parentheses
indicate that either move may be made.

\begin{center}
$
\begin{array}{| c | c | c | c | c | c | c | c | c | c | c | c || c |}
\hline
 B_0 & A_1  &  (B_1) &   &   &   &   &   &   &    & (B_7)  & A_8  & B_8 !  \\ \hline
  & (B_1)  & A_2  & B_2 !  & A_3  & (B_3)  &   &   &   &    &   &   &   \\ \hline
  &   &   &   & (B_3)  & A_4  & B_4 !  & A_5  & (B_5)  &    &   &   &   \\ \hline
  &   &   &   &   &   &   &  (B_5) & A_6  &  B_6 !  & A_7  &  (B_7) &   \\ \hline
\end{array}
$
\end{center}

Bob's first, third, fifth, and seventh moves may be either across
or down. Notice, however, that Bob's other moves are forced. If,
for example, $B_2$ is to $(2,2)$ then, by Lemma~\ref{closing},
Alice wins by moving to $(2,3)$ thereby completing a closing-off
sequence.

\subsection*{\normalsize 4.2 Playing the 10}

In a manner similar to playing the {\bf 12},
Alice may, at the beginning of the game,
force a sequence of moves that comprises 10 columns.
To do this, Alice plays down to $(0,1)$ on her first move
and, by the remark following Lemma~\ref{colone},
we may assume that Bob responds with $(1,1)$.

The complete sequence of moves is called
{\it playing the {\bf 10}}
and is shown in the diagram below.

\begin{center}
$
\begin{array}{| c | c | c | c | c | c | c | c | c | c || c |}
\hline
 X & & & & & & & & (B_6) & A_7 & B_7 ! \\ \hline
 A_1 & B_1 ! & A_2 & (B_2) & & & & & & & \\ \hline
  & & (B_2) & A_3 & B_3 ! & A_4 & (B_4) & & & & \\ \hline
  & & & & & (B_4) & A_5 & B_5 ! & A_6 & (B_6) & \\ \hline
\end{array}
$
\end{center}

Notice that, as in playing the {\bf 12},
Bob's third, fifth, and seventh moves are forced,
in order to prevent a closing-off move from Alice.

\vskip 30pt

\section*{\normalsize 5. Proof of Theorem~\ref{main}}

This section is devoted to the proof of our main result,
Theorem~\ref{main}.  The argument is in six cases, depending upon
the value of the odd integer $n$ modulo 12.

\subsection*{\normalsize 5.1 The case $n \equiv 1 \pmod{12}$}

\subsubsection*{\normalsize 5.11 $n = 1$}

The game $C_1 \times C_4$ is trivially a first player win.

\subsubsection*{\normalsize 5.12 $n > 1$}

In this case, $n = 13 + 12m$ for some $m \geq 0$.
Alice's winning strategy is to begin by playing the {\bf 10},
followed by playing the {\bf 12} $m$ times,
and finally to finish with a block of 3 columns.
The analysis is in two cases, according to Bob's second move in
the final block of 3 columns.

CASE 1:  Bob's second move in the final block of 3 is across

By Lemma~\ref{closing},
Alice wins by closing-off at $(n-1,3)$.

\begin{center}
$
\begin{array}{| c | c | c | c | c | c | c | c | c | c || c | c | c | c || c | c | c |}
\hline
 X & & & & & & & & (B) & A & B! & A & \cdots & A & B! & A & B \\ \hline
 A & B! & A & (B) & & & & & & & & (B) & \cdots & & & & A! \\ \hline
  & & (B) & A & B! & A & (B) & & & & & & \cdots & & & & B! \\ \hline
  & & & & & (B) & A & B! & A & (B) & & & \cdots & (B) & & & A \\ \hline
\end{array}
$
\end{center}

CASE 2:  Bob's second move in the final block of 3 is down

After Bob moves to $(n-2,1)$,
Alice responds with $(n-1, 1)$ and wins by Lemma~\ref{sink}.

\begin{center}
$
\begin{array}{| c | c | c | c | c | c | c | c | c | c || c | c | c | c || c | c | c |}
\hline
 X & & & & & & & & (B) & A & B! & A & \cdots & A & B! & A &  \\ \hline
 A & B! & A & (B) & & & & & & & & (B) & \cdots & & & B & A \\ \hline
  & & (B) & A & B! & A & (B) & & & & & & \cdots & & & &  \\ \hline
  & & & & & (B) & A & B! & A & (B) & & & \cdots & (B) & & &  \\ \hline
\end{array}
$
\end{center}

\subsection*{\normalsize 5.2 The case $n \equiv 3 \pmod{12}$}

\subsubsection*{\normalsize 5.21 $n = 3$}

Consider first the game $C_3 \times C_4$.
Alice's winning strategy is to begin the game
by playing across.
If Bob's first move is down then Alice responds
by moving across and wins by Lemma~\ref{sink}.

On the other hand, if Bob's first move is across
then Alice's second move is forced to be down.
If Bob's second move is down then Alice
plays the closing-off move $(2,3)$ and
wins on
her fourth move as shown below.

\begin{center}
$
\begin{array}{| c | c | c |}
\hline
 X & A_1 & B_1 \\ \hline
   &    & A_2 ! \\ \hline
   &   & B_2    \\ \hline
 B_3! & A_4 & A_3   \\ \hline
\end{array}
$
\end{center}

If Bob's second move is across then Alice wins on
her fifth move as shown below.

\begin{center}
$
\begin{array}{| c | c | c |}
\hline
 X & A_1 & B_1 \\ \hline
 B_2  & A_3   & A_2  ! \\ \hline
   & B_3!  &     \\ \hline
 A_5 & A_4 & B_4!   \\ \hline
\end{array}
$
\end{center}

\subsubsection*{\normalsize 5.22 $n > 3$}

We have $n = 15 + 12m$ for some $m \geq 0$.
Alice's winning strategy is to open by playing the {\bf 10}, then
to play the {\bf 12} $m$ times, and finally to
finish with a block of 5 columns.
By moving to $(n-1, 1)$ Alice wins by Lemma~\ref{sink}.

\begin{center}
$
\begin{array}{| c | c | c | c | c | c | c || c | c | c | c || c | c | c | c | c |}
\hline
 X & & & \cdots & & (B) & A & B! & A & \cdots & A & B! & A & (B) & & \\ \hline
 A & B! & A & \cdots & & & & & (B) & \cdots & & & (B) & A & B! & A \\ \hline
  & & (B) & \cdots  & & & & &  & \cdots & & & & & &  \\ \hline
  & & & \cdots & B! & A & (B) & & &  \cdots & (B) & & & & & \\ \hline
\end{array}
$
\end{center}

\subsection*{\normalsize 5.3 The case $n \equiv 5 \pmod{12}$}

Alice's winning strategy is to play the {\bf 12}
as often as required and then to close with the
block of 5 columns as shown below.
By moving to $(n-1, 1)$, Alice wins
by Lemma~\ref{sink}.

\begin{center}
$
\begin{array}{| c | c | c | c | c || c | c | c | c | c || c | c | c | c | c |}
\hline
 X & A & \cdots & (B) & A & B! & A & \cdots & (B) & A & B! & A & (B) & & \\
\hline
  & (B) & \cdots & & & & (B) & \cdots & & & & (B) & A & B! & A \\ \hline
  & & \cdots & & & & & \cdots & & & & & & & \\ \hline
  & & \cdots & A & (B) & & & \cdots & A & (B) & & & & & \\ \hline
\end{array}
$
\end{center}

\subsection*{\normalsize 5.4 The case $n \equiv 7 \pmod{12}$}

\subsubsection*{\normalsize 5.41 $n = 7$}

We consider first the game $C_7 \times C_4$.
Observe that Bob's third move is forced to be down,
otherwise Alice may move to
$(6,1)$ and win by Lemma~\ref{sink}.
As shown below, Alice may create a sink by moving
to $(3,3)$ on the second pass.

\begin{center}
$
\begin{array}{| c | c | c | c | c | c | c |}
\hline
 X & A_1 & (B_1) &  &  &  & \\ \hline
   & (B_1)  & A_2 & B_2 ! & A_3 & & \\ \hline
  &   &   &    & B_3 ! & A_4 & B_4 ! \\ \hline
 B_5 ! & A_6 !  & B_6 !  & A_7  &   &   &  A_5 \\ \hline
\end{array}
$
\end{center}

After Bob responds to $A_7$ with either $(3,0)$ or $(4,3)$,
Alice may force Bob's every move thereafter by
moving to $(4,0)$,
$(6,0)$, $(0,1)$, $(1,2)$
and finally to $(3,2)$ at which point she wins.

\subsubsection*{\normalsize 5.42 $n > 7$}

In this case, $n = 19 + 12m$ for some $m \geq 0$.
The analysis is in two cases depending upon Bob's
third move.

CASE 1:  Bob's third move is down

Alice's winning strategy is to play the {\bf 12}
$(m+1)$ times and then to finish with a block of
7 columns
as shown below.
Notice that Bob's penultimate move in the first pass
must be down, otherwise Alice may move to
$(n-1, 1)$ and win by Lemma~\ref{sink}.
Bob is forced to begin the second pass at $(0,3)$
and subsequently Alice creates a sink by moving to $(3,3)$.

\begin{center}
$
\begin{array}{| c | c | c | c | c | c | c | c | c || c | c | c | c | c | c | c |}
\hline
 X & A_1 & (B_1) & & & & \cdots & (B_7)  & A_8 & B! & A & (B)  &  &  &  &  \\ \hline
  & (B_1)  & A_2 & B_2 ! & A_3 &  & \cdots &  &   &  & (B)  & A & B! & A &  &  \\ \hline
  &  &  &  & B_3 & A_4  & \cdots & & & &  &  &  & B! & A & B! \\ \hline
 B! & A! & B! & A & & & \cdots & A_7 & (B_7)  &  &  &  &  &  &  & A \\ \hline
\end{array}
$
\end{center}

On the second pass, the first player to reach the last
column will be Alice at $(n-1,0)$ or Bob at $(n-1,1)$.
In either case, Alice begins the third pass at $(0,1)$
and, two moves later, wins the game at $(3,2)$.

CASE 2:  Bob's third move is across

Alice begins with a block of 14 columns.
She then plays the {\bf 12} $m$ times and concludes with
a block of 5 columns as shown below.
By Lemma~\ref{sink}, this is a winning strategy for Alice.

\begin{center}
$
\begin{array}{| c | c | c | c | c | c | c | c | c | c | c | c | c | c || c | c | c }
\hline
  X & A & (B)  &  &  &  &  &  &  &  &  &  & (B)  & A & B! & A & \cdots \\ \hline
  & (B)  & A & B! & A & B_3 & A & (B)  &  &  &  &  &  &  &  & (B)  & \cdots \\ \hline
  &  &  &  &  &  & (B)  & A & B! & A & (B)  &  &  &  &  &  & \cdots \\ \hline
  &  &  &  &  &  &  &  &  & (B)  & A & B! & A & (B)  &  &  & \cdots \\ \hline
\end{array}
$
\end{center}

\begin{center}
$
\begin{array}{ c | c | c | c || c | c | c | c | c |}
\hline
 \cdots & & (B) & A & B! & A & (B) & & \\ \hline
 \cdots & & & & & (B) & A & B! & A \\ \hline
 \cdots & & & & & & & & \\ \hline
 \cdots & B! & A & (B) & & & & & \\ \hline
\end{array}
$
\end{center}

\subsection*{\normalsize 5.5 The case $n \equiv 9 \pmod{12}$}

\subsubsection*{\normalsize 5.51 $n = 9$}

We consider first $C_9 \times C_4$.
The analysis is in two cases, depending upon
Bob's first move.

CASE 1:  Bob's first move is down

The analysis is in two subcases, depending
upon Bob's third move.

CASE 1A:  Bob's third move is across

Notice that Bob's fourth move must be down,
otherwise Alice may play her fifth move at
$(8,1)$ which wins by Lemma~\ref{sink}.
Alice begins the second pass at $(0,2)$ which
creates a sink.

\begin{center}
$
\begin{array}{| c | c | c | c | c | c | c | c | c |}
\hline
  X & A_1  &   &   &   &   &   &   &   \\ \hline
   & B_1  & A_2  & B_2 !  & A_3  & B_3  & A_4  &   &   \\ \hline
  A_6 &   &   &   &   &   & B_4 !  &  A_5 ! & B_5 !  \\ \hline
   &   &   &   &   &   &   &   &   \\ \hline
\end{array}
$
\end{center}

On the second pass, the first player to reach the
last column is Alice at $(8,0)$, or Bob at $(8,1)$
or $(8,3)$.
If Bob plays to $(8,1)$ then Alice replies to
$(0,1)$ and wins.
If Alice plays to $(8,0)$ then Bob is forced to
reply to $(8,1)$ after which Alice moves to $(0,1)$
and wins.
Finally, if Bob moves to $(8,3)$ then Alice moves
to $(8,0)$ and wins on her next move as described
above.

CASE 1B:  Bob's third move is down

On the second pass, Alice may create a sink by
moving to $(3,3)$, as shown below.

\begin{center}
$
\begin{array}{| c | c | c | c | c | c | c | c | c |}
\hline
 X & A_1 &   &  &  &  &  &  &   \\ \hline
  & B_1 & A_2 & B_2 ! & A_3 &  &  &  &   \\ \hline
  &  &  &  & B_3 & A_4 & B_4 ! & A_5 & (B_5)   \\ \hline
 B_6 ! & A_7 ! & B_7 ! & A_8 &  &  &  & (B_5)  & A_6  \\ \hline
\end{array}
$
\end{center}

On the second pass, the first player to reach the last column
is Alice at $(8, 0)$ or Bob at $(8, 1)$.
In either case, Alice begins the third pass at $(0, 1)$
and is able to force a win at $(3, 2)$.

CASE 2:  Bob's first move is across

Bob's fourth move is forced to be down
lest Alice reply with $(8,1)$ and win by Lemma~\ref{sink}.
On the second pass, Alice may create a sink by
moving to $(5,3)$, as shown below.

\begin{center}
$
\begin{array}{| c | c | c | c | c | c | c | c | c |}
\hline
  X & A_1  & B_1  & A_2  & (B_2)   &   &   &   &   \\ \hline
   &   &   & (B_2)  & A_3  & B_3 !  & A_4  &   &   \\ \hline
   &   &   &   &   &   & B_4 !  & A_5  & B_5 !   \\ \hline
  B_6 ! & A_7 !  & B_7 !  & A_8 !  & B_8 !  & A_9  &   &  & A_6  \\ \hline
\end{array}
$
\end{center}

On the second pass, the first player to reach the last column
is Alice at $(8, 0)$ or Bob at $(8, 1)$.
In either case, Alice begins the third pass at $(0, 1)$
and, three moves later, wins at $(5,2)$.

\subsubsection*{\normalsize 5.52 $n > 9$}

We have $n = 21 + 12m$ for some $m \geq 0$.
We require two cases, according to Bob's first move.

CASE 1:  Bob's first move is down

The analysis is in two subcases,
depending upon Bob's third move.

CASE 1A:  Bob's third move is across

Alice's winning strategy is to open with a block of $14$ columns,
followed by playing the {\bf 12} $m$ times,
and then to finish with a block of $7$ columns, as shown below.
Alice begins the second pass by moving to $(0,2)$,
thereby creating a sink at $(0,1)$.

\begin{center}
$
\begin{array}{| c | c | c | c | c | c | c | c | c | c | c | c | c | c || c | c | c }
\hline
 X & A &  &  &  &  &  &  &  &  &  &  & (B) & A & B! & A & \cdots  \\ \hline
   & B_1 & A & B! & A & B_3 & A & (B) & & & & & & & & (B) & \cdots \\ \hline
  A & & & & & & (B) & A & B! & A & (B) & & & & & & \cdots \\ \hline
 & & & & & & & & & (B) & A & B! & A & (B) & & & \cdots\\ \hline
\end{array}
$
\end{center}

\begin{center}
$
\begin{array}{ c | c | c | c || c | c | c | c | c | c | c |}
\hline
 \cdots &  & (B) & A & B! & A & (B) & & & & \\ \hline
 \cdots & & & & & (B) & A & B! & A & (B) & \\ \hline
 \cdots & & & & & & & & (B) & A & B! \\ \hline
 \cdots & B! & A & (B) & & & & & & & \\ \hline
\end{array}
$
\end{center}

The first player to reach the last column on the
second pass is Alice at $(n-1,0)$, or Bob at $(n-1,1)$
or $(n-1,3)$.
If Bob has moved to $(n-1,1)$ then Alice wins immediately
by moving to $(0,1)$.
If Alice has moved to $(n-1,0)$ then Bob is forced
to $(n-1,1)$ and Alice wins as above.
Finally, if Bob has moved to $(n-1,3)$ then Alice
wins by moving to $(n-1,0)$.

CASE 1B:  Bob's third move is down

Alice's winning strategy is to play the {\bf 12}
$(m+1)$ times, followed by a block of $9$ columns,
as shown below.
On the second pass, Alice moves to $(3,3)$ which
creates a sink at $(3,2)$.

\begin{center}
$
\begin{array}{| c | c | c | c | c | c | c | c | c | c | c | c || c | c | c }
\hline
 X & A &  &  &  &  &  &  &  &  & (B) & A & B! & A & \cdots \\ \hline
   & B_1 & A & B! & A &  & & & & & & & & (B) & \cdots \\ \hline
    & & &  & B_3  & A & B! & A & (B) & & & & & & \cdots  \\ \hline
  B! & A! & B! & A & & & & (B) & A & B! & A & (B) & & & \cdots \\ \hline
\end{array}
$
\end{center}

\begin{center}
$
\begin{array}{ c | c | c | c || c | c | c | c | c | c | c | c | c |}
\hline
 \cdots &  & (B) & A & B! & A & (B) & & & & & & \\ \hline
 \cdots & & & & & (B) & A & B! & A & (B) & & & \\ \hline
 \cdots & & & & & & & & (B) & A & B! & A & (B) \\ \hline
 \cdots & B! & A & (B) & & & & & &  &  & (B) & A \\ \hline
\end{array}
$
\end{center}

The first player to reach the last column on the
second pass is Alice at $(n-1,0)$ or Bob at $(n-1,1)$.
In either case, Alice may begin the third pass at
$(0,1)$ and is able to force a win at $(3,2)$.

CASE 2:  Bob's first move is across

The analysis is in two subcases,
depending upon Bob's fourth move.

CASE 2A:  Bob's fourth move is across

Alice's winning strategy is to open with a block of $16$ columns,
followed by playing the {\bf 12} $m$ times, and then to close
with a block of $5$ columns, as shown below.
By Lemma~\ref{sink}, Alice will win the game.

\begin{center}
$
\begin{array}{| c | c | c | c | c | c | c | c | c | c | c | c | c | c | c | c || c | c }
\hline
 X & A & B_1 & A & (B) &  &  &  &  &  & & & & & (B) & A & B! & \cdots \\ \hline
  & &  & (B) & A & B! & A & B_4  & A & (B) & & & & & & & & \cdots \\ \hline
   & & & & & & &  & (B)  & A & B! & A & (B) & & & & & \cdots  \\ \hline
  & & & & & & & & & & & (B) & A & B! & A & (B) & & \cdots\\ \hline
\end{array}
$
\end{center}

\begin{center}
$
\begin{array}{ c | c | c | c || c | c | c | c | c |}
\hline
 \cdots & & (B) & A & B! & A & (B)  & & \\ \hline
 \cdots & & & & & (B) & A & B! & A \\ \hline
 \cdots & & & & & & & & \\ \hline
 \cdots & B! & A & (B) & & & & & \\ \hline
\end{array}
$
\end{center}

CASE 2B:  Bob's fourth move is down

Alice's winning strategy is to open with a block of $14$ columns,
followed by playing the {\bf 12} $m$ times, and then to close
with a block of $7$ columns, as shown below.
On the second pass, Alice moves to $(5,3)$ which creates a sink
at $(5,2)$.

\begin{center}
$
\begin{array}{| c | c | c | c | c | c | c | c | c | c | c | c | c | c || c | c | c }
\hline
 X & A & B_1 & A & (B) &  &  &  &  & & & & (B) & A & B! & A & \cdots \\ \hline
  & &  & (B) & A & B! & A &    &   &     & & & & & & (B) & \cdots \\ \hline
  A & (B) & & & &  & B_4  & A & B! & A & (B) & & & & & & \cdots  \\ \hline
 (B) & A & B! & A! & B! & A & & & & (B) & A & B! & A & (B) & & & \cdots \\ \hline
\end{array}
$
\end{center}


\begin{center}
$
\begin{array}{ c | c | c | c || c | c | c | c | c | c | c |}
\hline
 \cdots & & (B) & A & B! & A & (B)  & & & & \\ \hline
 \cdots & & & & & (B) & A & B! & A & (B) &  \\ \hline
 \cdots & & & & & & & & (B) & A & B!  \\ \hline
 \cdots & B! & A & (B) & & & & & & & \\ \hline
\end{array}
$
\end{center}

On the second pass, the first player to reach the
last column is Alice at $(n-1,0)$ or Bob at
$(n-1,1)$ or $(n-1,3)$.
If Bob has moved to $(n-1,3)$ then Alice will
respond with $(n-1,0)$ so that, in any case,
Alice will begin the third pass at $(0,1)$
and will win at $(5,2)$.

\subsection*{\normalsize 5.6 The case $n \equiv 11 \pmod{12}$}

This is the only case in which Bob wins.
His winning strategy is to open with the
block of 11 columns shown below,
and then to play the {\bf 12} as often as required.
On the first pass, after Bob plays to $(n-1, 0)$, Alice is forced
to respond with $(n-1, 1)$.
Bob may then play the closing-off move $(n-1, 2)$.

\begin{center}
$
\begin{array}{| c | c | c | c | c | c | c | c | c | c | c || c | c | c }
\hline
  X &  (A_1)  &     &    &   &   &   &   &   & (A_7)   & B_7  &  A!   & B   & \cdots     \\
\hline
   (A_1) & B_1  &  A_2 ! & B_2  & (A_3)   &   &   &   &   &   &    &   & (A)  & \cdots    \\
\hline
    &    &     &  (A_3)  & B_3  & A_4 !  & B_4  &  (A_5) &   &   &    &     &    & \cdots   \\
\hline
    &    &     &    &    &     & (A_5)    & B_5  & A_6 !  & B_6   & (A_7)    &     &   & \cdots    \\
\hline
\end{array}
$
\end{center}

\begin{center}
$
\begin{array}{ c | c | c | c || c | c | c | c | c | c |}
\hline
 \cdots & & (A) & B & A! & B & \cdots & & (A) & B \\ \hline
 \cdots & & & & & (A) & \cdots & & & A! \\ \hline
 \cdots & & & & & & \cdots & & & B \\ \hline
 \cdots & A! & B & (A) & & & \cdots & A! & B & (A) \\ \hline
\end{array}
$
\end{center}

The proof of Theorem~\ref{main} is now complete.
 
\vskip 30pt

%\section*{\normalsize Acknowledgements}

%\vskip 30pt

\begin{thebibliography}{99}

\footnotesize 

\bibitem{berlekamp}
E.R. Berlekamp, J.H. Conway, and R.K. Guy,
{\it Winning Ways For Your Mathematical Plays},
A K Peters (2001).

\bibitem{fraenk1}
A.S. Fraenkel and S. Simonson,
Geography,
{\it Theoret. Comput. Sci. (Math Games)}
{\bf 110} (1993), 197--214.

\bibitem{fraenk2}
A.S. Fraenkel, E.R. Scheinerman and D. Ullman,
Undirected Edge Geography,
{\it Theoret. Comput. Sci. (Math Games)}
{\bf 112} (1993), 371--381.

\bibitem{fraenk3}
A.S. Fraenkel, A. Jaffray, A. Kotzig, and G. Sabidussi,
Modular Nim,
{\it Theor. Comput. Sci. (Math Games)}
{\bf 143} (1995), 319--333.

\bibitem{nowpoole}
R.J. Nowakowski and D.G. Poole,
Geography Played on Products of Directed Cycles,
{\it Games of No Chance},
MSRI Publications {\bf 29} (1996), 329--337.

\end{thebibliography}


\end{document}