\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{Shortlist 1996 C6}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 21}
\maketitle
\section*{Problem}
A finite number of coins are placed on an infinite row of squares.
A sequence of moves is performed as follows: at each stage a square
containing more than one coin is chosen.
Two coins are taken from this square;
one of them is placed on the square immediately to the left
while the other is placed on the square
immediately to the right of the chosen square.
The sequence terminates if at some point
there is at most one coin on each square.
Given some initial configuration,
show that any legal sequence of moves will terminate
after the same number of steps and with the same final configuration.
\section*{Video}
\href{https://www.youtube.com/watch?v=4oTU6jWCrzw&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/4oTU6jWCrzw}}
\newpage
\section*{Solution}
\textbf{First part}: We start by proving the procedure always terminates.
Index the squares by $\ZZ$.
\begin{claim*}
For any starting configuration,
there exists an interval $[A,B]$ such that
no coin may ever exit $B$.
\end{claim*}
\begin{proof}
Let $n$ be the largest index of a square with any coins.
Note that for any square $m > n$,
the following property is true:
if $m$ ever gains a coin,
then forever after, either $m$ or $m+1$ has a coin.
This follows since any move affecting either $m$ or $m+1$
will add a coin to at least one of them.
Thus, we make take $B = m + 2c$ where $c$ is the number of coins.
The choice of $A$ is similar.
\end{proof}
Now note that the sum of squares of indices of coins increases each step.
This shows that configurations may never repeat;
but there are finitely many configurations, ensuring termination.
\textbf{Second part}:
Suppose $S = (x_1, \dots, x_n)$ is a valid sequence of moves
that leads to an end state.
We perform the following procedure for $i = 1, \dots, n$.
\begin{itemize}
\ii Before the $i$'th move $s_i$,
look at the leftmost square which has more than one coin.
It must be operated on eventually,
since that is the only way it can lose coins.
Let $x_j$ be the first such move on this square.
\ii Rearrange the sequence so that this move $x_k$ comes next instead.
That is, apply the change
\[ (x_i, x_{i+1}, \dots, x_{j-1}, x_j)
\longmapsto \left( x_j, x_i, x_{i+1}, \dots, x_{j-1} \right). \]
Note that validity of the whole operation is preserved.
\end{itemize}
In this way, any valid sequence can be rearranged to a certain
\emph{canonical sequence} where one always operates on the leftmost possible square.
This implies that the lengths of all valid sequences are the same
(actually, they are permutations of each other),
and also that the ending states match.
\end{document}