\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{Shortlist 2013 A2}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 5}
\maketitle
\section*{Problem}
Prove that in any set of $2000$ distinct real numbers
there exist two pairs $a>b$ and $c>d$,
with \emph{either} $a \neq c$ or $b \neq d$,
such that
\[ \left\lvert \frac{a-b}{c-d} - 1 \right\rvert
< \frac{1}{100000}. \]
\newpage
\section*{Solution}
WLOG, we denote the set of $2000$ real numbers by
\[ S = \left\{ 0 = x_1 < x_2 < \dots < x_{2000} = 1 \right\}. \]
We proceed by contradiction and assume this is not the case.
\begin{claim*}
There exists $0 \le x < y \le 1$ in $S$ such that
\[ x-y < \left( \frac{1}{1 + 10^{-5}} \right)^{\binom{2000}{2}-1}. \]
\end{claim*}
\begin{proof}
Our contradiction hypothesis assumes
that any two differences of elements in $S$
differ by at least a factor of $1 + 10^{-5}$.
Since the largest difference is $1-0 = 1$
and there are $\binom{2000}{2}$ differences,
the conclusion follows.
\end{proof}
We let $0 \le x 0.499$ then
\[ 0 < \frac{y-0}{x-0} - 1 < \frac{\rho}{0.499} < 10^{-5} \]
as needed.
\ii If $ y < 0.501$ then similarly
\[ 0 < \frac{1-x}{1-y} - 1 < \frac{\rho}{0.499} < 10^{-5} \]
as needed.
\end{itemize}
\end{document}