\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{Shortlist 2008 N2}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 1}
\maketitle
\section*{Problem}
Let $a_1$, $a_2$, \dots, $a_n$ be
distinct positive integers for $n \ge 3$.
Prove that there exist distinct indices $i$ and $j$ such that
$a_i + a_j$ does not divide any of $3a_1$, $3a_2$, \dots, $3a_n$.
\newpage
\section*{Solution}
Assume for contradiction this is not true.
By sorting, we assume $a_1 > a_2 > \dots > a_n$.
We will suppose that $\gcd(a_1, \dots, a_n) = 1$,
else divide through.
\begin{claim*}
We have $a_i \equiv -a_1 \pmod 3$ for all $i > 1$.
\end{claim*}
\begin{proof}
If not then $a_1 + a_i$ divides some $3a_k$.
But $a_1 + a_i \perp 3$, so $a_1 + a_i$ divides some $a_k$.
This is impossible for size reasons.
\end{proof}
Since we assumed the sequence was relatively prime,
we have now that
\[ a_2 \equiv a_3 \equiv \dots \equiv a_n
\equiv -a_1 \not\equiv 0 \pmod 3. \]
We now work with only $a_1$, $a_2$, $a_3$.
The proof proceeds in three steps.
\begin{itemize}
\ii Again, $a_2 + a_3$ divides $3a_k$ for some $k$,
but since $a_2 + a_3 \not\equiv 0 \pmod 3$,
we find that $a_2 + a_3 \mid a_k$ for some $k$.
Hence in fact $\boxed{a_2 + a_3 \mid a_1}$.
\ii Meanwhile, $a_1 + a_2$ divides
either $3a_1$ or $3a_2$ for size reasons.
But actually, these two statements are equivalent,
since $a_1 + a_2$ divides their sum $3a_1+3a_2$.
Now from $2a_2 < a_1 + a_2 \mid 3a_2$,
we must have $\boxed{a_1 = 2a_2}$.
\ii Now $a_2 < a_2 + a_3 \mid a_1 = 2a_2$,
so we must have $a_2 + a_3 = 2a_2$
but then $a_2 = a_3$, contradiction.
\end{itemize}
This concludes the proof.
\begin{remark*}
Note that we can find pretty early on
that the $n=3$ case of the problem is sufficient:
the three largest numbers satisfy the condition anyways,
so there is no need any longer to look at $a_4$, $a_5$, \dots.
\end{remark*}
\end{document}