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

\begin{document}
\title{Shortlist 2009 C1}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 2}
\maketitle

\section*{Problem}
Consider $2009$ cards, each having one gold side and one black side,
lying on parallel on a long table.
Initially all cards show their gold sides.
Two players, standing by the same long side of the table,
play a game with alternating moves.
Each move consists of choosing a block of $50$ consecutive cards,
the leftmost of which is showing gold, and
turning them all over,
so those which showed gold now show black and vice versa.
The last player who can make a legal move wins.

\begin{enumerate}[(a)]
  \ii Does the game necessarily end?
  \ii Does there exist a winning strategy for the starting player?
\end{enumerate}



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

\newpage

\section*{Solution}
Interpret gold as $1$ and black as $0$.
The answer to (a) is obviously yes,
since viewing the number as a binary string of length $2009$
we find that it decreases at each step.

As for (b), we claim that
\begin{claim*}
The second player must win \emph{regardless} of what moves occur.
\end{claim*}
\begin{proof}
Consider the $50$th, $100$th, $150$th card, and so on,
up to the $2000$th card \emph{from the right}
(which is the $10$th card from the left).
Denote the set of these $40$ cards by $C$.

The number of $1$'s in $C$ must change by exactly $1$ every turn,
and it is initially $40$.
The game could only end when all cards in $C$ are zero.
So this can only occur on the first player's turn.
\end{proof}

\begin{remark*}
  It's important that the cards are counted from the right
  rather than from the left in (b).
  If one counts from the left, then the 2000th card from the left being gold
  does not imply a player has a legal move.
\end{remark*}

\end{document}
