Problem: A \emph{Nim-style game} is defined as follows. Two
positive integers $k$ and $n$ are specified, along with a finite
set $S$ of $k$-tuples of integers (not necessarily positive). At
the start of the game, the $k$-tuple $(n,0,0,\dots,0)$ is written
on the blackboard.

A legal move consists of erasing the tuple $(a_1,a_2,\dots,a_k)$
which is written on the blackboard and replacing it with
$(a_1+b_1,a_2+b_2,\dots,a_k+b_k)$, where $(b_1,b_2,\dots,b_k)$
is an element of the set $S$. Two players take turns making legal
moves, and the first to write a negative integer loses. In the
event that neither player is ever forced to write a negative
integer, the game is a draw.

Prove that there is a choice of $k$ and $S$ with the following
property: the first player has a winning strategy if $n$ is a
power of $2$, and otherwise the second player has a winning
strategy.

\end{enumerate}

Solution: Here we present a solution with $14$ registers and $22$ moves.
Initially $X=n$ and all other variables are zero.

\begin{center}
\scriptsize
\setlength{\tabcolsep}{3pt}
\begin{tabular}{l|rr|r|rrr|rrr|r|rr|rr}
&$X$&$Y$&Go&$S_X^0$&$S_X$&$S_X'$&$S_Y^0$&$S_Y$&$S_Y'$&Cl&$A$&$B$&Die&Die'\\\hline
Init&-1&&1&&&&&&&&&1&1&1\\
Begin&1&&-1&1&&&&&&&-1&1&&\\\hline
Sleep&&&&&&&&&&&1&-1&&\\\hline
StartX&&&&-1&1&&&&&&-1&1&&\\
WorkX&-1&&&&-1&1&&&&&-1&1&&\\
WorkX'&-1&1&&&1&-1&&&&&-1&1&&\\
DoneX&&&&&-1&&1&&&&-1&1&&\\
WrongX&-1&&&&&&-1&&&&&-1&&\\\hline
StartY&&&&&&&-1&1&&&-1&1&&\\
WorkY&&-1&&&&&&-1&1&&-1&1&&\\
WorkY'&1&-1&&&&&&1&-1&&-1&1&&\\
DoneY&&&&1&&&&-1&&&-1&1&&\\
WrongY&&-1&&-1&&&&&&&&-1&&\\\hline
ClaimX&-1&&&-1&&&&&&1&-1&1&&\\
ClaimY&&-1&&&&&-1&&&1&-1&1&&\\
FakeX&-1&&&&&&&&&-1&&-1&&\\
FakeY&&-1&&&&&&&&-1&&-1&&\\
Win&&&&&&&&&&-1&-1&&&\\\hline
PunA&&&&&&&&&&&&-2&&\\
PunB&&&&&&&&&&&-1&-1&&\\
Kill&&&&&&&&&&&&-1&-2&1\\
Kill'&&&&&&&&&&&&-1&1&-2
\end{tabular}
\end{center}

Now, the ``game'' is played as follows.
The mechanics are controlled by the \emph{turn counters} $A$ and $B$.

Observe the game starts with Alice playing Init.
Thereafter, we say that the game is
\begin{itemize}
  \ii In the \emph{main part} if $A+B = 1$,
  and no one has played Init a second time.
  \ii In the \emph{death part} otherwise.
\end{itemize}
Observe that in the main state,
on Alice's turn we always have $(A,B) = (1,0)$
and on Bob's turn we always have $(A,B) = (0,1)$.

\begin{claim*}
  A player who plays Init a second time must lose.
  In particular, a player who makes a move when $A=B=0$ must lose.
\end{claim*}
\begin{proof}
  Situations with $A+B \ge 2$ cannot occur during main part,
  so there are only a few possibilities.
  \begin{itemize}
  \ii Suppose the offending player is in a situation where $A=B=0$.
  Then he/she must play Init.
  At this point, the opposing player can respond by playing Kill.
  Then the offending player must play Init again.
  The opposing player now responds with Kill'.
  This iteration continues until $X$ reaches a negative number
  and the offending player loses.
  \ii Suppose Alice has $(A,B) = (1,0)$ but plays Init again anyways.
  Then Bob responds with PunB to punish her; he then wins as in the first case.
  \ii Suppose Bob has $(A,B) = (0,1)$ but plays Init again anyways.
  Alice responds with PunA in the same way. \qedhere
  \end{itemize}
\end{proof}

Thus we may assume that players avoid the death part at all costs.
Hence the second moves consist of Bob playing Sleep,
and then Alice playing Begin
(thus restoring the value of $n$ in $X$), then Bob playing Sleep.

Now we return to analysis of the main part.
We say the game is in \emph{state} $S$ for
$S \in \{S_X^0, S_X, S_X', S_Y^0, S_Y, S_Y', \text{Cl} \}$
if $S = 1$ and all other variables are zero.
By construction, this is always the case.
From then on the main part is divided into several phases:
\begin{itemize}
  \ii An \emph{$X$-phase}: this begins with Alice at $S_X^0$, and
  ends when the game is in a state other than $S_X$ and $S_X'$.
  (She can never return to $S_X^0$ during an $X$-phase.)
  \ii A \emph{$Y$-phase}: this begins with Alice at $S_Y^0$, and
  ends when the game is in a state other than $S_Y$ and $S_Y'$.
  (She can never return to $S_Y^0$ during a $Y$-phase.)
\end{itemize}

\begin{claim*}
Consider an $X$-phase in which $(X,Y) = (x,0)$, $x > 1$.
Then Alice can complete the phase without losing if and only if $x$ is even;
if so she begins a $Y$-phase with $(X,Y) = (0,x/2)$.
\end{claim*}
\begin{proof}
As $x >1$, Alice cannot play ClaimX since Bob will respond with FakeX and win.
Now by alternating between WorkX and WorkX',
Alice can repeatedly deduct $2$ from $X$ and add $1$ to $Y$,
leading to $(x-2,y+1)$, $(x-4,y+2)$, and so on.
(During this time, Bob can only play Sleep.)
Eventually, she must stop this process by playing DoneX, which begins a $Y$-phase.

Now note that unless $X=0$, Bob now has a winning move WrongX.
Conversely he may only play Sleep if $X=0$.
\end{proof}

We have an analogous claim for $Y$-phases.
Thus if $n$ is not a power of $2$, we see that Alice eventually loses.

Now suppose $n = 2^k$;
then Alice reaches $(X,Y) = (0,2^{k-1}), \; (2^{k-2}, 0), \; \dots$
until either reaching $(1,0)$ or $(0,1)$.
At this point she can play ClaimX or ClaimY, respectively;
the game is now in state Cl.
Bob cannot play either FakeX or FakeY, so he must play Sleep,
and then Alice wins by playing Win.
Thus Alice has a winning strategy when $n = 2^k$.