\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?
\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.
\textbf{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}
\]
\textbf{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}