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

\begin{document}
\title{ELMO 2010/3}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 75}
\maketitle

\section*{Problem}
Let $n > 1$ be a positive integer.
A 2-dimensional grid, infinite in all directions, is given.
Each 1 by 1 square in a given $n$ by $n$ square has a counter on it.
A move consists of taking $n$ adjacent counters in a
row or column and sliding them each by one space
along that row or column.
A returning sequence is a finite sequence of
moves such that all counters again fill the
original $n$ by $n$ square at the end of the sequence.
\begin{enumerate}[(a)]
\ii Assume that all counters are distinguishable except two,
which are indistinguishable from each other.
Prove that any distinguishable arrangement of counters in the $n$ by $n$ square
can be reached by a returning sequence.
\ii Assume all counters are distinguishable.
Prove that there is no returning sequence that switches two counters
and returns the rest to their original positions.
\end{enumerate}

\section*{Video}
\href{https://www.youtube.com/watch?v=rGoMTlJwq-I&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/rGoMTlJwq-I}}

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

\newpage

\section*{Solution}
Part (b) is good motivation for (a),
so we do that first.
We claim that we can only obtain even permutations.
The proof takes two observations:
\begin{itemize}
  \ii On the one hand, consider
  $\sum (x+y)$ across all counters at each step of the operation.
  It increases by $+n$ or $-n$ at every step.
  So any returning sequence must have an even number of operations.

  \ii On the other hand,
  at any time, we can consider the counter labeling
  as a permutation on $(\ZZ/n\ZZ)^2$
  (at any point, for any ordered pair of residues,
  exactly one counter occupies that residue).
  Then each operation is an $n$-cycle.
\end{itemize}
Hence, a returning sequence is a composition of an even
number of $n$-cycles; consequently,
it follows that each permutation is obtained has even \emph{parity}.
Therefore, it's impossible to achieve (b).

On the other hand, towards (a), we show any even permutation
is achievable.
\begin{claim*}
  We can permute any ``right triangle,'' i.e.
  \[
    \begin{bmatrix}
      \ddots & \dots & \dots & {\cdot^{\cdot^{\cdot}}} \\
      \vdots & A & B & \vdots \\
      \vdots & C & \bullet & \vdots \\
      {\cdot^{\cdot^{\cdot}}} & \dots & \dots & \ddots
    \end{bmatrix}
    \longrightarrow
    \begin{bmatrix}
      \ddots & \dots & \dots & {\cdot^{\cdot^{\cdot}}} \\
      \vdots & B & C & \vdots \\
      \vdots & A & \bullet & \vdots \\
      {\cdot^{\cdot^{\cdot}}} & \dots & \dots & \ddots
    \end{bmatrix}
    \qquad (1)
  \]
\end{claim*}
\begin{proof}
  Push the row with $A$ and $B$ left,
  push the column with $C$ and $A$ up,
  push the same row right,
  push the same column down.
\end{proof}
By composing these, we also get that
\[
  \begin{bmatrix}
    \ddots & \dots & \dots & {\cdot^{\cdot^{\cdot}}} \\
    \vdots & A & B & \vdots \\
    \vdots & C & D & \vdots \\
    {\cdot^{\cdot^{\cdot}}} & \dots & \dots & \ddots
  \end{bmatrix}
  \longrightarrow
  \begin{bmatrix}
    \ddots & \dots & \dots & {\cdot^{\cdot^{\cdot}}} \\
    \vdots & B & A & \vdots \\
    \vdots & D & C & \vdots \\
    {\cdot^{\cdot^{\cdot}}} & \dots & \dots & \ddots
  \end{bmatrix}
  \qquad (2)
\]
and
\[
  \begin{bmatrix}
    \ddots & \dots & \dots & \dots & {\cdot^{\cdot^{\cdot}}} \\
    \vdots & A & B & C & \vdots \\
    \vdots & \bullet & D & \bullet \vdots \\
    {\cdot^{\cdot^{\cdot}}} & \dots & \dots & \dots & \ddots
  \end{bmatrix}
  \longrightarrow
  \begin{bmatrix}
    \ddots & \dots & \dots & \dots & {\cdot^{\cdot^{\cdot}}} \\
    \vdots & B & C & A & \vdots \\
    \vdots & \bullet & D & \bullet \vdots \\
    {\cdot^{\cdot^{\cdot}}} & \dots & \dots & \dots & \ddots
  \end{bmatrix}
  \qquad (3)
\]
are both possible.

To finish, we number the counters in the following way:
\[
\begin{bmatrix}
  1 & 2 & 3 & \dots & n-1 & n \\
  2n & 2n-1 & 2n-2 & \dots & n+2 & n+1 \\
  2n+1 & 2n+2 & 2n+3 & \dots & 3n-1 & 3n \\
  4n & 4n-1 & 4n-2 & \dots & 3n+2 & 3n+1 \\
  \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\
\end{bmatrix}
\]
Observe that any two consecutive numbers are consecutive.
But we have the following fact:
\begin{lemma*}
  [Bubble sort]
  Let $N$ be any integer.
  Any permutation on $\{1, 2, \dots, N\}$
  is generated by the $N-1$ \emph{adjacent transpositions}
  $(1\; 2)$, $(2\; 3)$, \dots, $(N-1\; N)$.
\end{lemma*}
\begin{proof}
  This is a standard fact, most easily proved by induction on $N$.
\end{proof}
It follows an \emph{even} permutation on $\{1, 2, \dots, N\}$
is an even composition of adjacent transpositions.
But:
\begin{claim*}
  Any two adjacent transpositions for our $n^2$ counters
  can be obtained as the product
  of operations of the form $(1)$, $(2)$, $(3)$.
\end{claim*}
\begin{proof}
  By cases:
  \begin{itemize}
    \ii If both transpositions are horizontal,
    start with any operation of the form $(2)$
    and then ``move'' the two transpositions
    in place by using $(2)$ and $(3)$ repeatedly.
    \ii Same for two vertical.
    \ii If one horizontal and one vertical,
    then start with $(1)$ and use the same proof.
  \end{itemize}
\end{proof}
This completes the proof.

\end{document}
