\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$.



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

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