\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}}
\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}