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

\begin{document}
\title{JMO 2020/1}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 16}
\maketitle

\section*{Problem}
Let $n \ge 2$ be an integer.
Carl has $n$ books arranged on a bookshelf.
Each book has a height and a width.
No two books have the same height,
and no two books have the same width.

Initially, the books are arranged in
increasing order of height from left to right.
In a \emph{move}, Carl picks any two adjacent books
where the left book is wider and shorter than the right book,
and swaps their locations.
Carl does this repeatedly until no further moves are possible.

Prove that regardless of how Carl makes his moves,
he must stop after a finite number of moves, and when he does stop,
the books are sorted in increasing order of width from left to right.

\section*{Video}
\href{https://www.youtube.com/watch?v=r7j0oRtpErA&t=1190}{\texttt{https://youtu.be/r7j0oRtpErA}}

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

\newpage

\section*{Solution}
We say that a pair of books $(A,B)$ is \emph{height-inverted}
if $A$ is to the left of $B$ and taller than $A$.
Similarly define \emph{width-inverted} pairs.

Note that every operation decreases the number of width-inverted pairs.
This proves the procedure terminates,
since the number of width-inverted pairs starts at $\binom n2$
and cannot increase indefinitely.

Now consider a situation where no more moves are possible.
Assume for contradiction two consecutive books $(A,B)$ are still width-inverted.
Since the operation isn't possible anymore, they are also height-inverted.
In particular, the operation could never have swapped $A$ and $B$.
But this contradicts the assumption there were no height-inverted pairs initially.

\end{document}
