\documentclass[11pt]{scrartcl}
\usepackage{evan}

\begin{document}
\title{Shortlist 2004 C5}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 9}
\maketitle

\section*{Problem}
Let $N$ be a positive integer. Alice and Bob play a game.
First Alice writes down $1$ first.
Then every player (starting with Bob) sees the last number written.
If it is $n$, then that player may write either $n+1$ or $2n$,
but the written number cannot exceed $N$.
The player who writes $N$ wins. For which $N$ does Bob win?



\section*{External Link}
\url{https://aops.com/community/p251895}

\newpage

\section*{Solution}
Call this game the $N$-game (as we will induct on $N$).
The answer is that Bob wins the $N$-game
are exactly those that, when expressed in binary,
have no $1$'s in the $2^0$, $2^2$, $2^4$, \dots positions.

\paragraph{Setup.}
Define the \emph{$N$-table} as follows.
It has $N$ entries indexed by $\{1, \dots, N\}$.
\begin{itemize}
  \ii The $n$th entry is \textbf{losing} if and only if a player who
  sees this number on their turn wins; otherwise, it is \textbf{winning}.
  Hence by definition the last entry is always $L$
  (because a player who is faced with $N$ has just lost!).
  \ii Equivalently, here is a recursive description.
  We say $N$ is losing.
  Then, a given $n$ is winning if either $n+1$ or $2n$ is losing
  (ignoring $2n$ if $n > N/2$); else, it is winning.
  \ii Bob wins the $N$-game if and only if $1$ is $W$.
\end{itemize}
The tables are shown below for $N=12$, respectively.
\[
  \begin{array}{cccccccccccccc}
    1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\
    L & W & L & W & W & W & W & L & W & L & W & L \\ \hline
    1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\
    L & W & L & W & L & W & L & W & L & W & L & W & L \\ \hline
    1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\
    L & W & L & W & W & W & W & L & W & L & W & L & W & L
  \end{array}
\]

\paragraph{Proof.}
We start with the following claim.
\begin{claim*}
  If $N$ is odd, then Alice wins the $N$-game.
\end{claim*}
\begin{proof}
  Alice can force Bob to stay on odd numbers.
\end{proof}

We now address the case where $N$ is even.
\begin{claim*}
  Suppose $N \equiv 2 \pmod 4$ and $N > 2$.
  Then Bob wins the $N$-game
  if and only if he wins the $(N-2)$-game.
\end{claim*}
\begin{proof}
  In the $N$-table, we have $N$ is losing,
  $N-1$ is winning, $N-2$ is losing, and so on;
  until $N/2+1$ is losing.
  Thus $N/2$ is winning.

  Now note that we may delete $N$ and $N-1$ (the last two columns)
  from the table without affecting any other entries;
  indeed $N/2$ was winning anyways as $N/2+1$ is losing.
  Thus the $N$-table is
  the $(N-2)$-table with two extra columns at the end.
\end{proof}

\begin{claim*}
  Suppose $N \equiv 0 \pmod 4$ and $N > 4$.
  Then Bob wins the $N$-game
  if and only if he wins the $N/4$-game.
\end{claim*}
\begin{proof}
  In the $N$-table, we have $N$ is losing,
  $N-1$ is winning, $N-2$ is losing, and so on;
  until $N/2+1$ is winning.
  Now from this it follows $N/2$, $N/2-1$, \dots, $N/4+1$
  are all winning.

  Since this entire range of numbers is winning
  and thus don't affect any later numbers,
  we wind up finding the first $N/4$ numbers
  are just a copy of the $(N/4)$-table.
\end{proof}
These three claims imply the answer directly by induction.

\end{document}
