49th International Mathematical Olympiad Spain

Without loss of generality, let $0<a_1<a_2<\cdots <a_n$. One can also assume that $a_1,a_2,\dots ,a_n$ are coprime. Otherwise division by their greatest common divisor reduces the question to the new sequence whose terms are coprime integers.

Suppose that the claim is false. Then for each $i<n$ there exists a $j$ such that $a_n+a_i$ divides $3a_j$. If $a_n+a_i$ is not divisible by $3$ then $a_n+a_i$ divides $a_j$ which is impossible as $0<a_j\le a_n<a_n+a_i$. Thus $a_n+a_i$ is a multiple of $3$ for $i=1,\dots ,n-1$, so that $a_1,a_2,\dots ,a_{n-1}$ are all congruent (to $-a_n$) modulo $3$.

Now $a_n$ is not divisible by $3$ or else so would be all remaining $a_i$'s, meaning that $a_1,a_2,\dots ,a_n$ are not coprime. Hence $a_n\equiv r(\mathrm{mod}3)$ where $r\in \{1,2\}$, and $a_i\equiv 3-r(\mathrm{mod}3)$ for all $i=1,\dots ,n-1$.

Consider a sum $a_{n-1}+a_i$ where $1\le i\le n-2$. There is at least one such sum as $n\ge 3$. Let $j$ be an index such that $a_{n-1}+a_i$ divides $3a_j$. Observe that $a_{n-1}+a_i$ is not divisible by $3$ since $a_{n-1}+a_i\equiv 2a_i\not\equiv 0(\mathrm{mod}3)$. It follows that $a_{n-1}+a_i$ divides $a_j$, in particular $a_{n-1}+a_i\le a_j$. Hence $a_{n-1}<a_j\le a_n$, implying $j=n$. So $a_n$ is divisible by all sums $a_{n-1}+a_i$, $1\le i\le n-2$. In particular $a_{n-1}+a_i\le a_n$ for $i=1,\dots ,n-2$.

Let $j$ be such that $a_n+a_{n-1}$ divides $3a_j$. If $j\le n-2$ then $a_n+a_{n-1}\le 3a_j<a_j+2a_{n-1}$. This yields $a_n<a_{n-1}+a_j$; however $a_{n-1}+a_j\le a_n$ for $j\le n-2$. Therefore $j=n-1$ or $j=n$.

For $j=n-1$ we obtain $3a_{n-1}=k\left(a_n+a_{n-1}\right)$ with $k$ an integer, and it is straightforward that $k=1$ ($k\le 0$ and $k\ge 3$ contradict $0<a_{n-1}<a_n$; $k=2$ leads to $a_{n-1}=2a_n>a_{n-1}$). Thus $3a_{n-1}=a_n+a_{n-1}$, i.e. $a_n=2a_{n-1}$.

Similarly, if $j=n$ then $3a_n=k\left(a_n+a_{n-1}\right)$ for some integer $k$, and only $k=2$ is possible. Hence $a_n=2a_{n-1}$ holds true in both cases remaining, $j=n-1$ and $j=n$.

Now $a_n=2a_{n-1}$ implies that the sum $a_{n-1}+a_1$ is strictly between $a_n/2$ and $a_n$. But $a_{n-1}$ and $a_1$ are distinct as $n\ge 3$, so it follows from the above that $a_{n-1}+a_1$ divides $a_n$. This provides the desired contradiction.