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

\begin{document}
\title{EGMO 2024/4}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 146}
\maketitle

\section*{Problem}
For a sequence $a_1<a_2<\dots<a_n$ of integers,
a pair $(a_i,a_j)$ with $1\leq i<j\leq n$ is called \emph{interesting}
if there exists a pair $(a_k,a_\ell)$ of integers with $1\leq k<\ell\leq n$ such that
\[ \frac{a_\ell-a_k}{a_j-a_i}=2. \]
For each $n\geq 3$, find the largest possible number of interesting pairs
in a sequence of length $n$.

\section*{Video}
\href{https://www.youtube.com/watch?v=AawAbKQsCVM&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/AawAbKQsCVM}}

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

\newpage

\section*{Solution}
The answer is $\binom{n}{2} - (n-2)$.

\paragraph{Construction.}
We take $a_1 = 0$ and $a_i = 2^{i-2}$ for $i \ge 2$.
For example, when $n=5$ we get the following figure:

\begin{center}
\begin{asy}
  draw( (0,0)--(8,0), blue );
  real e = 0.2;
  draw( (0,-e)--(0,e), blue );
  draw( (1,-e)--(1,e), blue );
  draw( (2,-e)--(2,e), blue );
  draw( (4,-e)--(4,e), blue );
  draw( (8,-e)--(8,e), blue );
  label("$0$", (0,e), dir(90), blue);
  label("$1$", (1,e), dir(90), blue);
  label("$2$", (2,e), dir(90), blue);
  label("$4$", (4,e), dir(90), blue);
  label("$8$", (8,e), dir(90), blue);
  label("$a_1$", (0,-e), dir(-90), black);
  label("$a_2$", (1,-e), dir(-90), black);
  label("$a_3$", (2,-e), dir(-90), black);
  label("$a_4$", (4,-e), dir(-90), black);
  label("$a_5$", (8,-e), dir(-90), black);
\end{asy}
\end{center}
We see that all the pairs $(i,j)$ are interesting
\emph{except} for the cases where $j = n$ and $i \in \{1,2,\dots,n-2\}$.
Indeed:
\begin{itemize}
  \ii If $i=1$ and $j<n$, then $a_j - a_i = 2^{j-2} = \frac{a_{j+1}-a_j}{2}$.
  \ii If $i>1$ and $j<n$, then $a_j - a_i = \frac{2a_j-2a_i}{2} = \frac{a_{j+1}-a_{i+1}}{2}$.
  \ii If $i=n-1$ and $j=n$, then $a_j - a_i = 2^{n-3} = \frac{a_n - a_1}{2}$.
\end{itemize}

\paragraph{Proof of bound.}
Let $m = \frac{a_1 + a_n}{2}$.
Notice that
\begin{itemize}
  \ii If $a_j > m$, then $(1,j)$ is never interesting.
  \ii If $a_i < m$, then $(i,n)$ is never interesting.
\end{itemize}
This eliminates at least $(n-1)-1$ pairs,
one for each index $k$ with $a_k \neq m$.
(The pair $(1,n)$ is counted twice here.)
This gives the claimed bound.

\end{document}
