EGMO, 2024

Solution:

Answer. $\frac{1}{2}(n-1)(n-2)+1$.

Consider the numbers $a_{i} = 2^{i}$ for $2 \leq i \leq n$ and $a_{1} = 0$, and choose any pair $(i, j)$ with $1 \leq i < j \leq n$.
If $i = 1$, the pair $(1, j)$ is interesting for all $2 \leq j \leq n-1$, as $\frac{a_{j+1} - a_{1}}{a_{j} - a_{1}} = \frac{2^{j+1}}{2^{j}} = 2$.
If $i \geq 2$, the pair $(i, j)$ is also interesting for all $j$ such that $i+1 \leq j \leq n-1$, since $\frac{a_{j+1} - a_{i+1}}{a_{j} - a_{i}} = \frac{2^{j+1} - 2^{i+1}}{2^{j} - 2^{i}} = 2$.
In addition, the pair $(n-1, n)$ is interesting, as $\frac{a_{n} - a_{0}}{a_{n} - a_{n-1}} = 2$.
Hence, all pairs in which $j \leq n-1$, and additionally the pair $(n-1, n)$, are interesting, giving $\frac{1}{2}(n-1)(n-2)+1$ pairs in total.

Now, let's show that there can't be more interesting pairs. To this end we show that at least $\frac{1}{2} n(n-1) - \left(\frac{1}{2}(n-1)(n-2)+1\right) = n-2$ pairs are not interesting. Clearly, the pair $(1, n)$ is not interesting.
Let's make the following observation: if a pair $(i, j)$ is interesting and it's not $(1, n)$, then $a_{j} - a_{i}$ can't exceed $\frac{1}{2}(a_{n} - a_{1})$. (Since, if $(i, j)$ is interesting then $a_{l} - a_{k} = 2(a_{j} - a_{i})$ for some pair $(k, l)$. If then $2(a_{j} - a_{i}) > a_{n} - a_{1}$ we would have $a_{l} - a_{k} > a_{n} - a_{1}$, which is not possible.)
Finally, for any $2 \leq i \leq n-1$ consider pairs $(1, i)$ and $(i, n)$. If both of them are interesting, then, following the observation above, the only possibility is $a_{i} - a_{1} = a_{n} - a_{i} = \frac{a_{n} - a_{1}}{2}$. Clearly, this is possible for at most one $i$, so for all other $n-3$ values of $i$, at least one of pairs $(1, i)$ and $(i, n)$ is not interesting. Combining with the pair $(1, n)$, we get at least $n-2$ not interesting pairs in total, as desired.