\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{ToT Fall 2015 S-A7}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 53}
\maketitle
\section*{Problem}
Suppose $N$ children, no two of the same height, stand in a line.
The following two-step procedure is applied: first, the line is split
into the fewest possible number of groups so that in each group
all children are arranged from the left to the right in ascending order of their heights
(a group may consist of a single child).
Second, the order of children in each group is reversed,
so now in each group the children stand in descending order of their heights.
Prove that in result of applying this procedure $N - 1$ times the children
in the line would stand from the left to the right in descending order of their heights.
\section*{Video}
\href{https://www.youtube.com/watch?v=K_-dqUJhSUU&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/K\_-dqUJhSUU}}
\newpage
\section*{Solution}
We will use a \emph{threshold trick}:
fix a threshold $1 \le k < N$,
and during the process write $0$ for heights at most $k$
and $1$ for heights greater than $k$.
We are going to prove that under this process,
the $1$'s end up before all the $0$'s after at most $N-1$ steps.
(Note that the exact steps of the process depend on the original
numbers, and are not a function of $0$/$1$).
An example is given below for $N = 7$,
with the original heights on the left
and the modified process on the right for $k = 3$.
\[
\begin{bmatrix}
2 & 7 & 3 & 1 & 4 & 5 & 6 \\
7 & 2 & 3 & 6 & 5 & 4 & 1 \\
7 & 6 & 3 & 2 & 5 & 4 & 1 \\
7 & 6 & 3 & 5 & 2 & 4 & 1 \\
7 & 6 & 5 & 3 & 4 & 2 & 1 \\
7 & 6 & 5 & 4 & 3 & 2 & 1 \\
\end{bmatrix}
\longmapsto
\begin{bmatrix}
0 & 1 & 0 & 0 & 1 & 1 & 1 \\
1 & 0 & 0 & 1 & 1 & 1 & 0 \\
1 & 1 & 0 & 0 & 1 & 1 & 0 \\
1 & 1 & 0 & 1 & 0 & 1 & 0 \\
1 & 1 & 1 & 0 & 1 & 0 & 0 \\
1 & 1 & 1 & 1 & 0 & 0 & 0 \\
\end{bmatrix}
\]
Then, by varying the choice of $k$, the problem will be implied.
However, for fixed $i$, we prove the following claim:
\begin{claim*}
Suppose $0 \le i < k$ and $t \ge i$.
After $t$ steps, the $(i+1)$st zero from the right
is in position at least $\min(k + t - 2i, n-i)$.
\end{claim*}
An example for $k=3$ and $n=7$ is given below showing the equality case.
The three zeros are colored differently for illustration.
\[
\begin{bmatrix}
{\color{green!60!black}0} & {\color{blue}0} & {\color{red}0} & 1 & 1 & 1 & 1 \\
{\color{green!60!black}0} & {\color{blue}0} & 1 & {\color{red}0} & 1 & 1 & 1 \\
{\color{green!60!black}0} & 1 & {\color{blue}0} & 1 & {\color{red}0} & 1 & 1 \\
1 & {\color{green!60!black}0} & 1 & {\color{blue}0} & 1 & {\color{red}0} & 1 \\
1 & 1 & {\color{green!60!black}0} & 1 & {\color{blue}0} & 1 & {\color{red}0} \\
1 & 1 & 1 & {\color{green!60!black}0} & 1 & {\color{blue}0} & {\color{red}0} \\
1 & 1 & 1 & 1 & {\color{green!60!black}0} & {\color{blue}0} & {\color{red}0} \\
\end{bmatrix}
\]
\begin{proof}
Basically immediate by induction on $i$.
\end{proof}
Applying this claim ends the problem.
\end{document}