EGMO 2024 | Problem 4 | Solution - 14 April 2024

Problem 4. For a sequence a₁ < a₂ < · · · < a_nof integers, a pair ( a_i, a_j ) with 1 ≤ i < j ≤ n is called interesting if there exists a pair ( a_k, a_ℓ ) of integers with 1 ≤ k < ℓ ≤ n such that

$\frac{a_{l} - a_{k}}{a_{j} - a_{i}} = 2 .$

For each n ≥ 3, find the largest possible number of interesting pairs in a sequence of length n .

Solution

We show that the answer is $\binom{n-1}{2}+1$ . To see that this is optimal, we set $a_1 = 0$ and $a_i = 2^{i-2}$ for $i \geq 2$ and observe that every pair $(i, j)$ is interesting so long as $j < n$ , except for $(n-1, n)$ . There are exactly $\binom{n-1}{2} + 1$ such pairs, so we have the construction.

It remains to show that in general, we cannot do better than $\binom{n-1}{2}+1$ . We now show a way to find $n-2$ uninteresting pairs given any sequence $a_1 < a_2 < \dots < a_n$ .

First we have the pair $(1, n)$ . It is clearly uninteresting, since we certainly cannot have $a_n-a_1 \geq a_l-a_k = 2(a_n-a_1)$ . Now for each $1 < i < n$ we see that unless $a_i = \frac{a_1+a_n}{2}$ one of the pairs $(1, i)$ or $(i, n)$ is uninteresting, since one of $a_i-a_1$ and $a_n-a_1$ exceeds $(a_n-a_1)/2$ .

This gives us at least $1 + (n-3) = n-2$ pairs. This finishes, since now we have eliminated $n-2$ distinct pairs from a total of $\binom{n}{2}$ , leaving us with exactly $\binom{n-1}{2}+1$ , solving the problem.