Sprague-Grundy Theorem

An arrangement of turtles can be compared to a Nim board with:

• an odd number of stacks of size $j$, if the $j$th turtle is upside down,

• an even number of stacks of size $j$, if the $j$th turtle is the right side up.

The move of flipping the upside-down turtle $j$ corresponds to the Nim move of removing a single stack of size $j$ from the odd number of such stacks, leaving an even number of such stacks.

The move of flipping the upside-down turtle $j$ and flipping another turtle $k$, where $k<j$, corresponds to the Nim move of removing $j-k$ counters from one of the stacks of size $j$. There are an odd number of such stacks, and after the move there are an even number of stacks of size $j$ and one more stack of size $k$ than there used to be, so the evenness/oddness of the number of stacks of size $k$ has been switched.

This is not an exact correspondence between the Turning Turtles game and Nim, for the losing position in TT of all the turtles being the right way up (so no moves are available) corresponds to a Nim game where there is an even number of stacks of all sizes, and there are plays available here. However, such a Nim game is always a losing position for the player who has to play (if the player takes $x$ counters from a stack of size $y$, the other player does exactly the same, which is possible since there are an even number of stacks of size $y$ to begin with; this just puts the first player back in the position of having an even number of stacks of each size before him, and eventually all the piles will be exhausted, and the first player will have nowhere to go). Thus the losing position in TT corresponds to a more long drawn-out, but inevitable, loss in Nim. More theoretically, since the Nim sum $n\oplus n$ of a number with itself is always $0$, the Nim sum of a game with an even number of stacks of each size must be $0$, and hence that must be a losing position. Hence the lack of an exact correspondence does not matter.

Thus we can interpret a winning Nim strategy for TT as follows. For any layout of turtles, numbered $1$ to $n$ from left to right, let $A\subseteq \{1,2,\ldots,n\}$ be the set of upside-down turtles.

If $A = \varnothing$, you have lost.

Otherwise, calculate the disjoint binary sum $s(A)$ of the elements of $A$: $s(A) \; = \; \bigoplus_{j \in A} j$

If $s(A)=0$, you are in a losing position. You can choose to resign, cheat or make any play and hope for a mistake on your opponent's part.

If $s(A) \neq 0$, you are in a winning position. Let $d$ be the index of the most significant binary digit of $s(A)$, so that the binary expansion of $s(A)$ is $(s_ds_{d-1}\cdots s_1s_0)_2$ where $s_d=1$. Find $x \in A$ such that the $d$th binary digit of $x$ is $1$. This must be possible, since otherwise $s_d$ would be $0$. Calculate $y \,=\, s(A) \oplus x$. If $x$ and $y$ have binary expansions $(x_mx_{m-1}\cdots x_1x_0)_2$ and $(y_my_{m-1}\cdots y_1y_0)_2$ respectively (padding them with $0$s at the front to make them the same length) then:

• $s_j = 0$ for all $j > d$, and hence $y_j = x_j$ for all $j > d$.

• $x_d = 1$ and $y_d = 0$.

• $0 \le (x_{d-1}x_{d-2}\cdots x_1x_0)_2, (y_{d-1}y_{d-2}\cdots y_1y_0)_2 \le 2^d-1$.

From these facts it is clear that $y < x$.

• If $y=0$, you just flip the upside-down turtle $x$.

• If $y > 0$, you flip the upside-down turtle $x$ and also flip turtle $y$.

This strategy leaves your opponent with a set $B$ of upside-down turtles (the set $A$ with $x$ removed and, if necessary, $y$ either added or removed) such that $s(B) \; = \; s(A) \oplus x \oplus y \; = \; 0$ which is thus a losing position for your opponent.

Here is my take on the second problem...

After the first move, which must remove three adjacent vertices, the state of the game is a number of runs of adjacent vertices, with gaps between them corresponding to the vertices that have already been removed. We can regard this state as a Nim board where run of adjacent vertices corresponds to a stack, and the height of the stack is the number of adjacent vertices in the run. We can, as usual, describe a Nim board by a sequence of integers $s = (n_1,n_2,\ldots,n_k)$, representing $k$ stacks of heights $n_1,n_2, \ldots,n_k$.

After the first move of the game, the second player is faced with the Nim board $(n-3)$.

At each move, it is possible to:

• remove one counter from a stack, leaving no stack behind (when the stack just has height one, so that the run of adjacent vertices consists of just one vertex),

• remove two counters from a stack, leaving either no stack behind (when the stack has height two, so that the run of adjacent vertices consists of two neighbouring vertices) or one stack behind (when the stack has height three or more, so that the run of adjacent vertices consists of three or more adjacent vertices, and the vertex chosen to be removed, along with its neighbours, is one of the end ones),

• remove three counters from a stack, leaving either no stack behind (when the stack has height three, so that the run of adjacent vertices consists of three adjacent vertices, and the vertex chosen to be removed along with its neighbours is the middle one) or one stack behind (when the stack has height four or more, so we have four or more adjacent vertices and the vertex chosen to be removed along with its neighbours is one of the two vertices "one in" from the end) or two stacks behind (when the stack has height five or more, so we have five or more adjacent vertices and the vertex chosen to be removed along with its neighbours is neither one of the end vertices nor one of the "one in" vertices).

In the language of octal games, this is the game $0.137$, or Dawson's Chess.

The Nim number for a Nim board in the state $s = (n_1,n_2,\ldots,n_k)$ is the disjoint binary sum $G(s) \; = \; g(n_1) \oplus g(n_2) \oplus \cdots \oplus g(n_k)$ where $g$ is the Grundy function for this game, where $g(n)$ is defined recursively as the mex (the smallest nonnegative integer not in the list) of the Nim numbers of the Nim boards after one move has been applied to the Nim board with just one stack of height $n$. Thus $g(n) \; = \; \left\{ \begin{array}{ll} 0 & n=0 \\ \mathrm{mex}\{g(0)\}\; = \; 1 & n=1 \\ \mathrm{mex}\{g(0)\}\; = \; 1 & n=2 \\ \mathrm{mex}\{g(0),g(1)\} \; = \; 2 & n=3 \\ \mathrm{mex}\{g(1),g(2)\} \; = \; 0 & n=4 \\ \mathrm{mex}\left\{\begin{array}{l}g(n-2),g(n-3),g(1)\oplus g(n-4),\\ g(2)\oplus g(n-5),\ldots,g(n-5)\oplus g(2),g(n-4)\oplus g(1)\end{array}\right\} & n \ge 5 \end{array} \right.$ Standard theory tells us that one move applied to a Nim board with state $s$ with $G(s)=0$ leads to a Nim board with state $t$ such that $G(t) \neq 0$ and also that for any Nim board with state $s$ such that $G(s) \neq 0$ it is possible to find a single move with puts the Nim board into a state $t$ with $G(t) = 0$. Thus states with Nim score $0$ are losing states if you have to play next. Thus we deduce that the first player will win the game provided that the Nim number of the Nim board with one stack containing $n-3$ counters is $0$. Thus the first player will win precisely when $n \ge 3$ is such that $g(n-3)=0$.

The Grundy function $g$ for Dawson's Chess is completely known, and is eventually periodic of $34$. Basically, these are the values that $g(n)$ takes as $n\,\equiv\, 0,1,2,3,4,\ldots,33$ modulo $34$: $8\;1\;1\;2\;0\;3\;1\;1\;0\;3\;3\;2\;2\;4\;4\;5\;5\;9\;3\;3\;0\;1\;1\;3\;0\;2\;1\;1\;0\;4\;5\;3\;7\;4$ with the sole exceptions that $g(0) = g(14) = g(34) = 0$ and $g(16) = g(17) = g(51) = 2$.

Thus the first player wins when $n-3 = 0,14,34$ or else $n-3 \,\equiv\, 4,8,20,24,28$ modulo $34$. In other words, the first player wins when $n=3,17,37$ or else $n \,\equiv\, 7,11,23,27,31$ modulo $34$.

It would help to define what defines the winning position --- a player loses if there are no upside-down turtles available