WLOG we assume $ a_1<a_2<...<a_n$ we also use induction (base is practically trivial) so for every $ {k}\leq{n-1}$ there exists a pair described in the task $ a_n+a_{n-1}> \frac{3}{2} a_i$ for all $ i<n$ so one of the following statements is true $ a_n,a_{n-1}$ is the desired pair or $ \frac{a_n+a_{n-1}}{3}=a_k$ for some $ k<n$ or $ a_n+a_{n-1} | 3a_n$ which is equivalent to $ a_n+a_{n-1} | 3a_{n-1}$ so this is equal to the previous case. We shall now prove that either the statement of the problem is true or this sequence has more than n elements (what is of course a contradiction). If the first case is true we are done so we only need to consider second one. if $ k=n-1$ we get $ a_n=2a_{n-1}$ and by induction we know that there is a pair $ a_i+a_j, i<j<n$ such that $ a_i+a_j$ ł $ 3a_k$ for all $ k<=n-1$ and because $ a_n=2a_{n-1}$ we also have $ a_i+a_j$ ł $ 6a_{n-1}=3a_n$ so this pair is the desired one otherwise we know we must have $ \frac{a_n+a_{n-1}}{3}, a_{n-1},a_n$ are elements of this sequence we continue same conclusions and get that every expression of the following kind must be in this sequence $ \frac{a_{n-1}+\frac{3^k-1}{2}a_n}{3^k}$ for every k and either there is to much of them( more than n) either they aren't integers in both ways it is impossible so we have proven our statement

OK, I solved this a long time ago. Forgot to post the solution here.

Suppose $a_1<a_2<\dots<a_n$. We also suppose $(a_1,a_2,\dots,a_n)=1$. We suppose opposite, that for every $a_i+a_j$ exists $a_k$ such that $a_i+a_j|3a_k$. Consider pairs $a_n+a_i$ for $1\le i \le n-1$. For every $i$ there is $j$ such that $a_n+a_i|3a_j$. Now if $3$ doesn't divide $a_n+a_i$ then $a_n+a_i|a_j$ but $a_n>a_j$ which is a contradiction. So we proved that $a_1,a_2,\dots a_{n-1}$ are all congruent to $-a_n$ modulo $3$. Because their gcd is 1, we conclude that none of our numbers is divisible by 3. Now we conclude that 3 doesn't divide $a_i+a_j$ for $1 \le i<j<n$. Now observe $a_{n-2}+a_{n-1}>a_{n-1}$ and 3 doesn't divide that sum so $a_{n-2}+a_{n-1}|a_{n}$. When we consider pair $a_n+a_{n-1}$ it can divide $3a_n$ which easily gives $a_n=2a_{n-1}$. It can divide $3a_{n-1}$ (it will be equal) which also easily gives $a_n=2a_{n-1}$. Now suppose that $a_n+a_{n-1}|3a_i$ for some $i<n-1$. Because $a_n+a_{n-1}>2a_i$ it has to be $3a_i=a_n+a_{n-1}\ge 2a_{n-1}+a_{n-2} > 3a_{n-2}\ge 3a_i$ which is a contradiction so we conclude $a_n=2a_{n-1}$. We got $a_{n-1}+a_{n-2}|a_n=2a_{n-2}$ so because $a_{n-1}+a_{n-2}>a_{n-1}$ we have that $a_{n-1}+a_{n-2}=2a_{n-1}$ so $a_{n-1}=a_{n-2}$ and that is a contradiction so the problem is proven.

My solution: Let $[n]=\{1,2, \dots ,n\}$. Assume to the contrary that there exists a sequence $a_1,a_2, \dots ,a_n$, such that for all distinct integers $i,j \in [n]$, there exists $k \in [n]$ such that $a_i+a_j \mid 3a_k$. Denote this statement by $P(i,j)$, and call such a sequence ugly. We wish to show that no ugly sequence exists. Now, suppose that $\gcd(a_1,a_2, \dots ,a_n)=d$. Taking $a_i=d \cdot b_i$, and using our statement $P(i,j)$, we get that $b_i$ is also ugly. So WLOG assume that $\gcd(a_1,a_2, \dots ,a_n)=1$. Also WLOG suppose that $a_1>a_2> \dots >a_n$. $P(1,j)$ gives that there exists $k \in [n]$, such that $a_1+a_j \mid 3a_k$. If, for some $j \in [n]$, $3 \nmid a_j+a_1$, then $a_j+a_1 \mid a_k \Rightarrow a_k \geq a_j+a_1$, a contradiction to the assumption that $a_1$ is maximum. So we get that $3 \mid a_j+a_1 \text{ } \forall j \in [n]$. Call this property as the triple property of an ugly sequence. Also, if $3 \mid a_r$ for some $r \in [n]$, then $3 \mid a_1$, which in turn gives that $3 \mid a_s$ for all $s \in [n]$, a contradiction to our assumption that their GCD is one. Thus, we get that $3$ doesn't divide any of the $a_i$'s. Now, consider $P(i,2)$, where $i>2$. Then there exists $k \in [n]$ such that $a_i+a_2 \mid 3a_k$. Note that if $3 \mid a_i+a_2$, then using the triple property, we get that $3$ divides $a_1-a_2$ as well as $a_1+a_2$, which in turn gives that $3 \mid 2a_1 \Rightarrow 3 \mid a_1$, that was earlier proved by us to be impossible. This means that $3 \nmid a_i+a_2$, and so $a_i+a_2 \mid a_k \Rightarrow a_i+a_2 \leq a_k$, which is only possible if $k=1$. Thus, $a_i+a_2 \mid a_1$ for all $i \in [n]$ and $i>2$. So we basically have that $a_2+a_i \leq a_1$. Now, from $P(1,2)$, we have that there exists $k \in [n]$ such that $a_1+a_2 \mid 3a_k$. CASE-1 $(k>2)$ Note that $a_1+a_2 \leq 3a_k \Rightarrow 3a_k-a_2 \geq a_1 \geq a_2+a_k \Rightarrow a_k \geq a_2$. This gives that either $k=1$ or $k=2$, a contradiction to our assumption. CASE-2 $(k=2)$ We have $a_1+a_2 \leq 3a_2 \Rightarrow a_1 \leq 2a_2$. Also $a_1+a_2 \mid (3a_2)-(a_1+a_2) \Rightarrow a_1+a_2 \mid 2a_2-a_1$. As $2a_2>a_1$, we get that $a_1+a_2 \leq 2a_2-a_1 \Rightarrow 2a_1 \leq a_2$, a contradiction to our assumption that $a_1$ is maximum. CASE-3 $(k=1)$ In this case, we are given that $a_1+a_2 \mid 3a_1$. As $a_1<a_1+a_2<2a_1$, we must have that $a_1+a_2=\frac{3a_1}{2}$. This gives that $a_1=2a_2$. But then, as $a_i+a_2 \mid a_1=2a_2$ for $i>2$, and cause $a_2<a_i+a_2<2a_2$, we get that there is no possible integral value of $a_i$ for all $i>2$. Thus, we again arrive at a contradiction. Summing up all the cases together, we get the result that no ugly sequence exists. Hence, done. $\blacksquare$

Here is a solution that is equivalent to bobthesmartypants' solution but with an optimization to avoid subcasework. Assume the contrary, so for all distinct $i, j$ there is $k$ so that $a_i + a_j \mid 3a_k$. WLOG $a_1<a_2< \dots < a_n$ and $\gcd(a_1,a_2,\dots,a_n)=1$. For each $i=1, 2, \dots, n-1$, we have $a_n + a_i \mid 3a_k$ for some $k$, but for size reasons we must have $3 \mid a_n + a_i$. This implies that $a_1 \equiv a_2 \equiv \dots \equiv a_{n-1} \equiv -a_n \pmod{3}$, and since we assumed they are all relatively prime we have $a_i \not \equiv 0 \pmod{3}$. Thus, for all $i<j \leq n-1$, we have $a_i + a_j \equiv 2a_i \not \equiv 0 \pmod{3} \quad (\heartsuit)$. Now, suppose $a_n + a_{n-1} \mid 3a_k$. Note that if $k=n$, then $a_n + a_{n-1} \mid 3a_{n-1}$ anyways so assume $k \le n-1$. Since $a_n + a_{n-1} > 2a_k$, we must have $a_n + a_{n-1} = 3a_k$ and so $a_n = 3a_k - a_{n-1}$. Now consider the number $a_{n-1} + a_{n-2}$. By $(\heartsuit)$, it is not divisible by $3$, so if it divides $3a_j$ it must divide $a_j$. For size reasons this must be $a_n$. So, we have$$a_{n-1} + a_{n-2} \mid a_n = 3a_k - a_{n-1} \le 2a_{n-1},$$forcing $a_{n-2}=a_{n-1}$, a contradiction. $\blacksquare$

An easier solution by induction: Key lemma: If $m > \frac{n}{2}$, then $m$ does not divide $n$. We proceed by induction on $n$, the number of distinct positive integers. Base case: $n=3$ WLOG let $a_1 < a_2 < a_3$. By our lemma, we know that $a_3 + a_2$ does not divide $3a_2$ or $3a_1$. Case i) $a_3 + a_2$ does not divide $3a_3$: Then we simply take $2, 3$ as the desired indices $i, j$ Case ii) $a_3 + a_2$ does divide $3a_3$: Since $\frac{3a_3}{3}<a_3 + a_2 <\frac{3a_3}{1}$, we must have that $a_3 + a_2 = 1.5a_3$ , or rather $a_3 = 2a_2$. Now consider $a_3 + a_1 = 2a_2 + a_1$. We know that $a_3 + a_1$ does not divide $a_1$ and $a_2$ by our key lemma. Furthermore, $$\frac{3a_3}{3} = 2a_2 < a_3 + a_1 = 2a_2 + a_1 < 3a_2 = \frac{3a_3}{2}$$. Thus $a_3 + a_1$ does not divide $a_3$ either, and we take $3, 1$ as our desired indices $i, j$. Inductive step: We shall assume the result is true for $n-1$ distinct positive integers. Thus note that for any $a_1 < a_2 < ... a_n$ we can find indices $2 \le i < j \le n$ such that $a_i + a_j$ does not divide any of $3a_2, 3a_3, ... 3a_n$ (by the inductive hypothesis). Furthermore, $a_i + a_j > 2a_1$, and once again by our key lemma $a_i + a_j$ does not divide $3a_1$ either, completing the inductive step.

Solution from Twitch Solves ISL: 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. Claim: We have $a_i \equiv -a_1 \pmod 3$ for all $i > 1$. 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. $\blacksquare$ 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. 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}$. 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}$. 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. This concludes the proof. 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$, ...

Are size arguments commonly used in number theory (like the one above)?

FTSoC suppose that for each pair $(i, j)$, we have $a_i + a_j \mid a_k$ for some index $k$. Since all $a_i$ are all distinct by the problem statement, and because this question is in the Size NT unit, we are motivated to assume the terms are in decreasing order $a_1 > a_2 > \ldots > a_n$. Furthermore, we can also assume that $\gcd(a_1, a_2, \ldots , a_n) = 1$ because otherwise we can divide out the GCD and the problem setup remains identical. I claim that for all $i \geq 2$ we have $3 \mid a_1 + a_i$. Suppose otherwise, and that $3 \nmid a_1 + a_i$ for some index $i$. Then, since $a_1 + a_i \mid 3a_j$ for some $j$, and because $\gcd(a_1 + a_i, 3) = 1$, we must have $a_1 + a_i \mid a_j$, a clear contradiction by our size assumption. Now get stuck for 45 minutes due to lack of skill and foresight. Then ponder the meaning of life and eventually think back to SIZE. Rewriting the above we have\[a_2 \equiv a_3 \equiv \ldots \equiv a_n \equiv -a_1 \pmod 3.\]Note that this common value mod $3$ cannot be zero or else $3$ divides all terms, a contradiction to our assumption that $\gcd(a_1, a_2, \ldots , a_n) = 1$. Let's consider the larger elements. $a_2 + a_3 \mid 3a_k$ for some index $k$. Note that $a_2 + a_3 \equiv -2a_1 \not\equiv 0 \pmod 3$ so in fact $a_2 + a_3 \mid a_k$ so by size $k = 1$ and thus $a_2 + a_3 \mid a_1$. (This actually motivates the previous step) Furthermore, $a_1 + a_2 \mid 3a_l$ for some index $l$. Clearly $l \geq 3$ is bad due to size. Hence, we must have $a_1 + a_2 \mid 3a_1$ or $3a_2$, which actually turn out to be equivalent statements. Either way, take $a_1 + a_2 \mid 3a_2$. Note that $a_1 + a_2 \geq 2a_2$ and the only factor of $3a_2$ greater than $2a_2$ is $3a_2$ so we must have $a_1 = 2a_2$. But combined with $a_2 + a_3 \mid a_1$, this forces $a_3 = a_2$, which is impossible, and we are done. $\blacksquare$ Lastly, realize that solution is the same as Evan's

WLOG let $a_1 < a_2 < a_3 < \cdots < a_n$. Assume ftsoc that the problem isn't true and for every $i, j$, there exists $k$ such that $a_i + a_j | 3a_k$. Claim: $a_1 \equiv a_2 \equiv \cdots \equiv a_{n-1} \pmod{3}$. Proof: Since $a_n + a_1 | 3a_k$ for some $k$, if $3 \nmid a_n + a_1$, we would have $a_n + a_1 | a_k$, but for size reasons that is impossible since it would mean $a_k \leq a_n < a_n + a_1 \leq a_k$. Hence $a_1 + a_n \equiv 0 \pmod{3}$. Similarly $a_2 + a_n \equiv 0 \pmod{3}, \cdots a_{n-1} + a_n \equiv 0 \pmod{3}$, therefore $a_1 \equiv a_2 \equiv \cdots a_{n-1} \pmod{3}$. $\qquad \blacksquare$ Now if $a_1 \equiv a_2 \equiv \cdots a_{n-1} \equiv 0 \pmod{3}$, then we would have $a_n \equiv 0 \pmod{3}$ as well, so we the problem would be equivalent when dividing all $a_i$ by $3$. Therefore we may assume that none of the $a_i$'s are divisible by $3$, as it would mean all the others are, too. We know that $$\begin{cases} a_i\equiv 1 \pmod{3} \qquad \text{for } 1 \leq i \leq n-1 \\ a_n \equiv 2 \pmod{3} \end{cases}$$or, alternatively, $$\begin{cases} a_i \equiv 2 \pmod{3} \qquad \text{for } 1 \leq i \leq n-1 \\ a_n \equiv 1 \pmod{3} \end{cases}$$ We know that $a_{n-1} + a_{n-3} | 3a_k$, however, $3 \nmid a_{n-1} + a_{n-3}$, so $a_{n-1} + a_{n-3} | a_k$. For obvious size reasons, $k = n$, hence, $a_{n-1} + a_{n-3}|a_n$. If we have $a_{n-1} + a_{n-3} = a_n$, we would arrive at a contradiction because $$a_{n-1} + a_{n-3}|a_n$$and $$a_{n-1} + a_{n-2}|a_n$$cannot hold at the same time, because it would mean $a_n = a_{n-1} + a_{n-3} < a_{n-1} + a_{n-2} \leq a_n$, absurd. Hence, $2(a_{n-1} + a_{n-3}) \leq a_n$. But if $2(a_{n-1} + a_{n-3}) = a_n$, we examine both sides modulo 3 and it doesn't work because $2(a_{n-1} + a_{n-3}) \equiv 2(1+1) = 1 \pmod{3}$ whereas $a_n \equiv 2 \pmod{3}$ or, in the second case $2(a_{n-1} + a_{n-3}) \equiv 2(2+2) = 2 \pmod{3}$ wheras $a_n \equiv 1 \pmod{3}$. Therefore, $a_n \geq 3(a_{n-1} + a_{n-3})$. But we also know that $a_n + a_{n-1} | 3a_k$ for some $k$. If $k \leq n-1$, we would have $a_n < 3a_{n-1}$. But that is a contradiction to $a_n \geq 3(a_{n-1} + a_{n-3})$, as shown above. Hence $a_n + a_{n-1} | 3a_n \implies a_n + a_{n-1} | 3a_n - 2(a_n + a_{n-1}) = a_n - 2a_{n-1}$. However $a_n > 2a_{n-1}$ (since $a_n \geq 3(a_{n-1} + a_{n-3})$). So that means $a_n + a_{n-1}$ divides a positive integer less than $a_n$, contradiction. So, our hypothesis was incorrect, and there exists $i, j$ such that $a_i + a_j$ does not divide $3a_k$ for any $k$. $\qquad \blacksquare$

April wrote: Let $ a_1$, $ a_2$, $ \ldots$, $ a_n$ be distinct positive integers, $ n\ge 3$. Prove that there exist distinct indices $ i$ and $ j$ such that $ a_i + a_j$ does not divide any of the numbers $ 3a_1$, $ 3a_2$, $ \ldots$, $ 3a_n$. Proposed by Mohsen Jamaali, Iran For the sake of contradiction, let us say that given any pair of indices $(i, j)$ we can find a proper index $k$ such that $a_i + a_j \mid 3a_k$. Without loss of generality let $a_i < a_j$ if $i < j$. We scale down all $a_i$ such that $\text{gcd}(a_1, a_2, a_3 \dots a_n) = 1$ (basically scaling down or up all the numbers would not change the assumption as the ratio $a_i + a_j : 3a_k$ hasn't changed) Consider $a_n + a_j$ for all $j$ such that $1 \leq j \leq n-1$. We see that $a_n + a_j \lvert 3a_k$ for some $k$ such that $1 \leq k \leq n-1$, but $a_n + a_j > a_n > a_k$ and so $3 \lvert a_n + a_j$, which means that $a_1 \equiv a_2 \equiv a_3 \dots a_{n-2} \equiv a_{n-1} = k \pmod{3}$, and due to scaling, $k \in \{ 1, 2 \}$. (We use the fact that if $d \lvert n$ then $d \leq \left \lceil \dfrac{n}{2} \right \rceil$ multiple times in this paragraph) We see that $a_{n-1} + a_{n-2} \lvert 3a_j \implies a_{n-1} + a_{n-2} \lvert a_j = a_n$ as $a_{n-1} + a_{n-2} \equiv 2 a_{n-1} \not\equiv 0 \pmod{3}$ and $a_n + a_{n-1} > a_{n-1} \geq a_j$ for $j \leq n-1$. Therefore, we see that if $a_n + a_{n-1} \lvert 3a_k$ for some $k \in \mathbb{N}$, then $a_n + a_{n-1} \geq 2a_{n-1} + a_{n-2} > 3a_k$ for all $k \leq n-2$ implying that $k = n-1$ or $n$, but if $k = n$ then $a_n + a_{n-1} \lvert 3(a_n + a_{n-1}) - 3a_n = 3a_{n-1}$ and since $a_n + a_{n-1} > 2a_{n-1} > \left \lceil \dfrac{3a_{n-1}}{2} \right \rceil$, we must have that $a_n + a_{n-1} = 3a_{n-1}$ or $a_n = 2a_{n-1}$. Now, $a_{n-1} + a_{n-2} \lvert a_j = 2a_{n-1}$ and since $a_{n-1} + a_{n-2} > a_{n-1} = \left \lceil \dfrac{2a_{n-1}}{2} \right \rceil$, we must have that $2a_{n-1} = a_{n-1} + a_{n-2}$ or $a_{n-1} = a_{n-2}$ which is the desired contradiction.

For the sake of contradiction, assume that for every distinct indices $i$ and $j$ we have some $r$, so that $a_i + a_j \mid 3a_r$. Let $a_n> a_{n-1}> \cdots > a_2> a_1$. Let us consider $a_n+a_i \mid 3a_r$, where $1\leq i \leq n-1$, note that as $a_n+a_i>a_r$, then we must have indeed that $a_n+a_i\equiv 0 \pmod{3}$ for all $1\leq i \leq n-1$. Now let us take any $1\leq i,j\leq n-1$ and we see that $a_i+a_j\mid 3a_r$, thus if $a_i+a_j\equiv 0 \pmod{3}$, we actually obtain that every $a_i$ is divisible by $3$, note that dividing this $3$ out, we get the same problem and thus we divide all possible $3$'s out and we get that for any $1\leq i,j\leq n-1$, $a_i+a_j\not \equiv 0 \pmod{3}$, i.e. $a_i+a_j\mid a_r$. Also it is worth noting that $i=n-1$ and $j=n-2$ imply $r=n$, since $a_r \geq a_{n-1}+a_{n-2}>a_{n-1}\implies r=n$. Now we consider the divisibility, $a_n+a_{n-1}\mid 3a_x$, where $1\leq x \leq n$. If $x=n$, then $a_n+a_{n-1}\mid a_n-2a_{n-1}\implies a_n=2a_{n-1}$. If $x=n-1$, then $a_n+a_{n-1}\mid 2a_{n-1}-a_n\implies a_n=2a_{n-1}$, in both cases $a_{n-1}+a_{n-2}\mid a_n=2a_{n-1}\implies a_{n-1}=a_{n-2}$, which contradicts distinctness. Thus, we get $x\leq n-2$, and we write the following divisibilites, $a_n+a_{n-1}\mid 3a_x$ and $a_x+a_{x+1}\mid a_r$ for some $1\leq r \leq n$, therefore $$a_n+a_{n-1}\leq 3a_x<a_x+a_x+a_{x+1}\leq a_x+a_r,$$which is impossible, as $x\leq n-2$.

Who needs mods Without loss of generality, let $a_1=\max\{a_1,\ldots,a_n\}$. Since $n \geq 3$, there either exists some $i \neq 1$ such that $a_i>\tfrac{1}{2}a_1$ or $a_i<\tfrac{1}{2}a_1$. We now consider the following two cases: Case 1: For all $i \neq 1$ we have $a_i\leq \tfrac{1}{2}a_1$. Pick $m$ such that $a_m \neq \tfrac{1}{2}a_1$ and $a_m$ is maximal. Then we have $a_1+a_m>3a_m\geq 3a_i$ if $a_i<\tfrac{1}{2}a_1$, so $a_1+a_m \nmid 3a_i$ in this case. We also have $\frac{3a_1}{2}>a_1+a_m>a_1>\tfrac{3a_1}{4}$, so $a_1+a_m$ is strictly between two consecutive divisors of both $3a_1$ and $\tfrac{3a_1}{2}$ if the latter is an integer, so $a_1+a_m \nmid 3a_1,3a_i$ if $a_i=\tfrac{1}{2}a_i$. Thus $a_1+a_m \nmid 3a_1,\ldots,3a_n$. Case 2: There exists $i \neq 1$ with $a_i>\tfrac{1}{2}a_1$. Let $m$ be a positive integer with $a_m>\tfrac{1}{2}a_1$ such that $a_m$ is minimal. In this case, we have $$3a_i\geq 3a_m>a_1+a_m>\tfrac{3a_1}{2}\geq\tfrac{3a_i}{2}$$for all $a_i>\tfrac{1}{2}a_1$, so $a_1+a_m \nmid 3a_i$ in this case. We also have $a_1+a_m>\tfrac{3a_1}{2}\geq 3a_i$ for all $a_i\leq \tfrac{1}{2}a_1$, so $a_1+a_m \nmid 3a_i$ in this case as well, implying $a_1+a_m \nmid 3a_1,\ldots,3a_n$.

FTSOC assume the contrary. WLOG assume $\gcd(a_1,a_2, \dots,a_n)=1$ and $a_n>a_{n-1}> \dots>a_1$. Claim : $a_1 \equiv a_2 \equiv \dots \equiv{a_{n-1}} \equiv{-a_n} \pmod{3}$ It suffices to prove that $3 \mid a_i+a_n \hspace{.1 cm} \forall \hspace{.01 cm}n$. Suppose not, then we can find $j$ satisfying $a_i+a_n \mid a_j$ which is a size contradiction. Claim : $2a_{n-1} \geq a_n$ Note that we can write $a_n+a_{n-1} \mid 3a_i$ for some $i \leq n-1$ since $a_n+a_{n-1} \mid 3a_n \implies a_n+a_{n-1} \mid 3a_{n-1}$. This means that $a_n \leq 3a_i -a_{n-1} \leq 2a_{n-1}$ as desired Claim : For any $n>3$, we get $a_1=a_2= \dots=a_{n-2}$ By the previous claims, we have either $a_1 \equiv a_2 \equiv \dots \equiv{a_{n-1}} \equiv{-a_n} \equiv{1} \pmod{3} $ or $a_1 \equiv a_2 \equiv \dots \equiv{a_{n-1}} \equiv{-a_n} \equiv{2} \pmod{3}$. Note that $3 \nmid a_i+a_{n-1}$ for all $i \leq n-2$. The assumption guarantees that we can find $j$ such that $a_i+a_{n-1} \mid a_j$ (since it is coprime to $3$) which is a size contradiction unless $j=n$. As a result, $$a_i+a_{n-1} \mid a_n\hspace{.1 cm} \forall \hspace{.01 cm} i \leq n-2$$But we also have $a_n \leq 2a_{n-1}$, and therefore $a_n=a_{n-1}+a_i$ for all such $i$, implying the result. This is clearly a contradiction. The $n=3$ case is easy to handle by some casework ; Let the numbers be $a_1,a_2,a_3$. We have $a_3=a_1+a_2$ (shown previously), so rewrite this as $a,b,a+b$($b>a$) We must have $a+2b \mid 3a_i$ for some $i$. If $i=1, a+2b \mid 3a$, contradicting size. If $i=2, a+2b \mid 3b \implies a+2b \mid b-a$, contradicting size. Finally, if $i=3, a+2b \mid 3a+3b-a-2b=2a+b$ which contradicts size too, and we are done $\blacksquare$

It is not difficult to prove that the statement is true for $n=3$. For $n>3$, suppose that there are $n$ distinct positive integers making the problem false, and WLOG let $a_1 > a_2 > \ldots >a_n$, and cancel out any common factors of $3$ among all numbers (as the two sequences are equivalent for this problem). Suppose that there was an $i$ such that $2\le i\le n$ and $a_1+a_i$ is not a multiple of $3$. Then $a_1+a_i$ dividing one of $3a_1, 3a_2, \ldots, 3a_n$ is equivalent to dividing one of $a_1, a_2, \ldots, a_n$, which is impossible due to size. Therefore $a_1+a_i$ is divisible by $3$ for all $2\le i\le n$. If $a_1$ was divisible by $3$, then all $a_i$ are divisible by $3$, but we divided out all common factors of $3$, contradiction. Therefore either $a_1\equiv 1\pmod 3$, making all other terms $2$ mod $3$, or $a_1\equiv 2\pmod 3$, making all other terms $1$ mod $3$. As we know the statement is true for $n=3$, there must be $i$ and $j$ so that $1\le i, j \le 3$ and $a_i+a_j$ does not divide $3a_1, 3a_2$, or $3a_3$. Case 1: $(i,j)=(2,3)$ is a working pair. It suffices to show that $a_2+a_3$ does not divide $3a_4, 3a_5, \ldots, 3a_n$. However, as $a_2+a_3$ is not a multiple of $3$, this is equivalent to showing $a_2+a_3$ does not divide $a_4, a_5, \ldots, a_n$, which cannot happen due to size reasons. Case 2: $(i,j)=(2,3)$ does not work. Therefore, either $(i,j)=(1,2)$ or $(i,j)=(1,3)$ work (or both). As $a_2+a_3$ is not a multiple of $3$, for it to divide $3a_1, 3a_2$, or $3a_3$, it must divide $a_1, a_2$, or $a_3$. $(a_2+a_3)|a_1$ is the only option for size reasons, making $a_2+a_3\le a_1 \Rightarrow a_3 < \frac{1}{2}a_1$. It suffices to show that the working pair does not divide one of $3a_4, 3a_5, \ldots, 3a_n$. However, as $a_1 + a_2 > a_1+a_3 > 3a_3 > 3a_4$, whichever pair works, it is greater than any of $3a_4, 3a_5, \ldots, 3a_n$, resolving this case. The proof is complete.

Can someone check this solution real quick? Its different than the one's posted I think. WLOG the set of elements is sorted such that $a_n$ is the largest and $a_1$ is the smallest. Now notice that if we find some $i$ such that $a_n+a_i\not\equiv 0\pmod{3}$ then we would be done because if there exists some $k$ such that $a_n+a_i\mid 3a_k$ then $3a_k=a_n+a_i$ or $3a_k=2(a_n+a_i)$ because of a simple bounding argument. Obviously none of these equations have a solution so we are done. So now we must have \[ a_1\equiv a_2\equiv\dots\equiv a_{n-1}\equiv -a_n\pmod{3}. \] Establishing this, we will proceed with a contradiction-construction argument. First choose two numbers $a_1, a_n$ such that $a_n>a_1$ and $a_n\neq 2a_1$. We will designate $a_n$ as the largest in the set and each element that we add in the set must be smaller than $a_n$. Case 1. $2a_1>a_n$ Define $f(x)=\frac{x+a_n}{3}$. Since we are trying to achieve a contradiction, we must add $f(a_1)$ to the set. If we added $2f(a_1)$ to the set then $2f(a_1)$ would become the new largest which we don't want to happen. Then we continue and add $f(f(a_1))$ the the set in order to satisfy the condition. Notice that this process is decreasing meaning that \[ f(a_1)>f(f(a_1))>f(f(f(a_1)))>\dots. \]Note that in each step of the process we will assume that it will remain an integer. Thus we will eventually end at $\left\lfloor \frac{a_n}{2} \right\rfloor +1$. Case 1.1. $a_n$ is even The process will end at $\frac{a_n}{2}+1$ and it is easy to see that $a_n+\frac{a_n}{2}+1\equiv 1\pmod{3}$. Case 1.2. $a_n$ is odd It will end at $\frac{a_n-1}{2}+1=\frac{a_n+1}{2}$. It is also easy to see that $a_n+\frac{a_n+1}{2}\equiv 2\pmod{3}$ so we are done. Case 2. $2a_1<a_n$. Like the above case we will define $f(x)=\frac{x+a_n}{3}$. If we decide to use $2f(a_1)$ then this will be a continuation of Case 1 and we would be done. So we must use $f(a_1)$ and $f(f(a_1))$ and so on. Now notice that this process is increasing meaning that \[ f(a_1)<f(f(a_1))<f(f(f(a_1)))<\dots. \]Note that in each step of the process we will assume that it will remain an integer. Case 2.1. $a_n$ is even This process will eventually end at $\frac{a_n}{2}-1$ and since $a_n+\frac{a_n}{2}-1\equiv 2\pmod{3}$ we are done with this case. Case 2.2. $a_n$ is odd This process will end at $\left\lfloor \frac{a_n}{2} \right\rfloor=\frac{a_n-1}{2}$ and since $a_n+\frac{a_n-1}{2}\equiv 1\pmod{3}$ we are done. Combining all of these cases gives us the desired contradiction and we are done. $\blacksquare$

Here's a different solution without looking at divisibility by $3$. Also, we will more strongly show that we can fix $a_j = \max(a_1,a_2,\ldots,a_n)$. WLOG $a_1 < a_2 < \ldots < a_n$. We will more strongly show that $\exists ~ 1 \le i \le n-1$ such that $a_i + a_n$ does not divide any of $3a_1,\ldots,3a_n$. Assume contrary. For each $i$, let $f(i)$ be the least index such that $a_i + a_n \mid 3a_{f(i)}$. Note if $a_i + a_n \mid 3a_n$, then $a_i + a_n \mid 3a_i$. Hence $f(i) \ne n$ for all $i$. Call $i$ good if $a_i > \frac{a_n}{2}$. Claim: At least one $i$ is good. Proof: If $f(n-1) \ne n-1$, then $a_n + a_{n-1} \mid 3a_{f(n-1)} \implies a_n + a_{n-1} = 3a_{f(n-1)}$ forcing $f(n-1)$ to be good. Otherwise, if $f(n-1) = n-1$ then we must $a_{n-1} = \frac{a_n}{2}$. Now we look at $f(n-2)$. As $a_{n-2} \ne a_{n-1} = \frac{a_n}{2}$, so $f(n-2) \ne n-1,n-2$. We then get $f(n-2)$ to be good. $\square$ Now observe that if $i$ is good, then $a_n + a_i = 3a_{f(i)}$. $f(i)$ is good. $i$ is not a fixed point of $f$. Start with any good $k$. Look at $k,f(k),f(f(k)),\ldots$. It must contain some cycle $\mathcal C$. Let $l$ be the largest element of $\mathcal C$. Choose $x,y \in \mathcal C$ such that $f(x) = l$ and $f(l) = y$. Then, \begin{align*} a_n + a_l = 3a_y \qquad , \qquad a_n + a_x = 3a_l \\ \implies 3a_l - 3a_y = a_x - a_l \implies 4a_l = a_x + 3a_y \end{align*}But this contradicts $a_l > a_x,a_y$. $\blacksquare$

guptaamitu1 wrote: A different solution without looking at divisibility by $3$: WLOG $a_1 < a_2 < \ldots < a_n$. We will more strongly show that $\exists ~ 1 \le i \le n-1$ such that $a_i + a_n$ does not divide any of $3a_1,\ldots,3a_n$. Assume contrary. For each $i$, let $f(i)$ be the least index such that $a_i + a_n \mid 3a_{f(i)}$. Claim: $f(i) \ne n ~~ \forall ~ i$. Proof: If $f(i) = n$ for some $i$, then $a_i + a_n \mid 3a_n$ along with size reasons would yield $a_n = 2a_i$, but then $a_i + a_n \mid 3a_i$, which contradicts the minimality of $f(i)$. $\square$ what if the $a_i+a_n=\frac32 a_n$;

So $a_i + a_n = \frac{3}{2} a_n$ implies $a_n = 2a_i$. Also, one doesn't even need that since $a_i + a_n \mid 3a_n$ without size reasons is also enough to imply $a_i + a_n \mid 3a_i$ (as $a_i + a_n \mid 3a_n + 3a_i$).

Isn't it too easy for N2? Assume contrary. Let $a_1<a_2<\cdots <a_n$. Claim 1: $a_n<2a_{n-1}$. Proof: Assume FTSOC $a_n\geq 2a_{n-1}$. If $a_n>2a_{n-1}$,then since $3a_{n-1}<a_n+a_{n-1}$ we get $a_n+a_{n-1}\mid 3a_n$, but then $a_n+a_{n-1}\mid 3a_{n-1}$,which is contradiction. So $a_n=2a_{n-1}$. $3a_{n-2}<a_n+a_{n-2}$. If $a_n+a_{n-2}\mid 3a_{n-1}$ then we get $a_{n-2}=a_{n-1}$,which is contra. If $a_n+a_{n-2}\mid 3a_n$,then $2a_{n-2}=a_n$,which again implies $a_{n-2}=a_{n-1}$, contra. Claim 2: $2a_1\le a_n$. Proof: Assume $2a_1>a_n$. Then $a_n+a_1<3a_1$, which is contradiciton. From Claim 1 and Claim 2 we get that there is some $m$ such that $2a_{m-1}\le a_n<2a_m$.Let $a_n+a_m\mid 3a_k$. $3a_{m-1}<a_n+a_m$, so $k\geq m \implies a_k\geq a_m$. $a_k<a_n+a_m<3a_m\le 3a_k \implies 2a_n+2a_m=3a_k$, but since $3a_k=2a_n+2a_m>3a_n\implies a_k>a_n$, we get contradiction. So done.

If $n=3$, let $a_1=a$, $a_2=b$, and $a_3=c$ for simplicity. Assume not and $a<b<c$. We have that $b+c|3a \implies 3a=b+c$, $b+c|3b \implies c=2b$, or $b+c|3c \implies c=2b$. If $c=2b$, then $a+2b|3a \implies a=b$, contradiction or $a+2b|6b$ contradiction as well. This means $3a=b+c$. We have $a+c|3a \implies c=2a$, contradiction, $a+c|3c \implies c=2a$, contradiction, or $a+c|3b$. Thus $4a-b = \frac{3b}{2}$ or $4a-b=3b \implies a=b$, contradiction. Thus $8a=5b$. Let $a=5k$, $b=8k$, and $c=7k$, contradiction to $b<c$ so we are done. Otherwise $n \ge 4$. Assume not. WLOG, assume $a_1<a_2< \cdots < a_n$ and $\gcd(a_1,a_2, \dots, a_n)=1$ (otherwise just divide the common factor out). Assume $3 \nmid a_i+a_n$ for some $1 \le i \le n-1$. This means that $a_i+a_n|a_k$ for some $k$. However $a_i+a_n > a_n \ge a_k$, contradiction. This means $3|a_i+a_n$ for all $1 \le i \le n-1$. Note that if $a_{n-1}+a_n | 3a_n$, we would have $a_{n-1}=\frac{a_n}{2}$. Otherwise, $a_{n-1}+a_n \le 3a_{n-1} \implies a_{n-1} \ge \frac{a_n}{2}$. This means $a_{n-1} \le \frac{a_n}{2}$. Assume that for all $1 \le k \le n-2$, $3 \nmid a_k+a_{n-1}$. Note that $a_k+a_{n-1}|a_n$ from similar reasoning to above. Note that $a_1+a_{n-1}$ and $a_2+a_{n-1}$ are distinct divisors of $a_n$, so one of them is less than $\frac{a_n}{2}$, so $a_{n-1} \le \frac{a_n}{2}$ contradiction. This means $3|a_k+a_{n-1}$ for some $1 \le k \le n-2$. Using this it is easy to see $3|a_k$ for all $k$ contradiction so we are done.

Assume that $\gcd(a_1, a_2, \ldots, a_n) = 1$ since we can divide out any common factors. WLOG $a_1<a_2<\cdots < a_n$. Suppose FTSOC that the problem condition was not true. Claim: $a_i\equiv -a_n \pmod 3$ for any $1\le i<n$. Proof: Suppose not. Then $a_i + a_n$ divides $3a_k$ for some $k$, and since $\gcd(3, a_i + a_n) = 1$, we have $a_i + a_n \mid a_k$, which is impossible due to size reasons. $\square$ This also implies $3\nmid a_i$ for any $i$ (otherwise $3$ would divide all of$a_1,a_2,\ldots, a_n$). Now, we have $3\nmid a_{n-1} + a_{n-2}$, so $a_{n-1} + a_{n-2}$ divides $a_k$ for some $k$. Due to size reasons, we must have $k=n$, and $a_{n-1} + a_{n-2} \le a_n$. We have $a_{n-1} + a_n \ge 2a_{n-1}+ a_{n-2} > 3a_{n-2}$, so $a_{n-1} + a_n$ must divide $3a_n$ or $3a_{n-1}$. Since $a_{n-1} + a_n < 2a_n$, and the only divisor of $3x$ greater than $x$ can be $3x/2$ or $3x$, we have $a_{n-1} + a_n \in \{1.5a_n, 3a_{n-1}\}$, both of which imply $a_n = 2a_{n-1}$. Now, $a_{n-1} + a_{n-2}\mid 2a_{n-1}$, so we must have $a_{n-2} = a_{n-1}$, contradiction.

First, scale all the $a_i$'s down until $\gcd(a_1,a_2,\dots,a_n)=1$. Also let $a_1<a_2<\dots<a_n$. Assume for the sake of contradiction that $a_i+a_j\mid 3a_k$ for some $k$, for all $(i,j)$. Then, suppose there exists $i\in \{1,2,\dots, n-1\}$ such that $3\nmid a_n+a_i$, then \[a_n+a_i\mid 3a_k\implies a_n+a_i\mid a_k\implies a_n+a_i\le a_k\le a_n,\]absurd. Thus, $3\mid a_n+a_i$ for all $i$. Additionally, $a_1$, $a_2$, $\dots$, $a_{n-1}$ are congruent $\pmod 3$. If they are all congruent to $0\pmod 3$, then $3\mid a_n+a_1\implies 3\mid a_n$ which contradicts the original coprime assumption. Therefore, $a_{n-1}+a_i$ is not divisible by $3$ for all $i=1$, $2$, $\dots$, $n-2$. Now, \[a_{n-1}+a_i\mid 3a_k\implies a_{n-1}+a_i\mid a_k\implies a_{n-1}+a_i \le a_k\]so $a_{n-1}<a_{k}$, implying $k=n$ for all $i$. In particular, $a_{n-1}+a_{n-2}\mid a_n$ which implies $a_{n}+a_{n-1}\ge 2a_{n-1}+a_{n-2} > 3a_{n-2}$. Thus, $a_{n}+a_{n-1}\mid 3a_{n-1}$ or $3a_n$. If it is the former, then note $2(a_{n}+a_{n-1}) > 3a_{n-1}$ so $a_{n}+a_{n-1}=3a_{n-1}$, implying that $a_n=2a_{n-1}$. Thus, $a_{n-1}+a_i\mid 2a_{n-1}$, implying $a_i=a_{n-1}$, absurd. Thus, $a_n+a_{n-1}\mid 3a_n$. Note that factors of $3a_n$ over $a_n$ are just possibly $\tfrac32 a_n$ or $3a_n$. The first one just goes back to the previous paragraph, whereas the second one is definitely not possible by size. Therefore, this is not possible.

Assume not. Then assume WLOG $a_1<a_2<\dots<a_n$. Divide $a_i$ by its gcd so that $\gcd(a_1,a_2,\dots,a_n)=1$. Note that if $3\nmid a_k+a_n$, then $a_k+a_n$ divides one of $a_1,a_2,\dots,a_n$ which is impossible by size. If $3\mid a_n$ then the gcd can't be $1$, so $3\nmid a_n$. But then $3\nmid a_{n-2}+a_{n-1}$, so $a_{n-2}+a_{n-1}\le a_n$. Now note that $a_{n-1}+a_n>a_{n-2}+a_n\ge a_{n-2}+a_{n-2}+a_{n-1}>3a_{n-2}$. Therefore, $a_{n-1}+a_n$ and $a_{n-2}+a_n$ divide $3a_{n-1}$ or $3a_n$. If $a_{n-1}+a_n\mid 3a_n$, then $2a_{n-1}=a_n$. If $a_{n-1}+a_n\mid 3a_{n-1}$, then $a_n=2a_{n-1}$. So either way, $a_n=2a_{n-1}$. If $a_{n-2}+a_n\mid 3a_{n-1}$, then $a_{n-2}=a_{n-1}$, impossible. If $a_{n-2}+a_n\mid 3a_n$, then $2a_{n-2}=a_n$, so $a_{n-2}=a_{n-1}$, again impossible. We win! $\blacksquare$

Order the elements as $a_1<a_2<\cdots<a_n$. Note that $a_n \equiv -a_i \pmod 3$ for every $i$, as otherwise $a_i + a_n \mid a_k$ for some $k$ (as the $3$ drops), which is impossible for size. Using this, it suffices to look at $a_{n-2}, a_{n-1}, a_n$. Notice that the first condition implies $a_{n-2} \equiv a_{n-1} \pmod 3$, so in particular $a_{n-2} + a_{n-1} \mid a_n$. Furthermore, $3(a_{n-2} + a_{n-1}) > a_n$, as otherwise $a_n + a_{n-1} > 3a_{n-2}$. Combined with the fact that $a_n \equiv -a_{n-1} \pmod 3$, this is enough to imply $$a_{n-2}+a_{n-1} = a_n.$$But then, $$a_n + a_{n-1} = 2a_{n-1} + a_{n-2} \geq 3a_{n-2}$$unless $a_{n-1} = a_{n-2}$. On the other hand, if it equals $3a_{n-1}$, we get $a_{n-1} = a_{n-2}$ again; both contradict distinctness.

We'll proceed induction on $n$. Base case can be done by hand. Assume the contrary, for every $i$ and $j$, there exists $k$ such that $a_i + a_j \mid 3a_k$. WLOG, we can assume $a_1 < a_2 < \dots < a_n$. If there exists $i$ such that $3 \nmid a_n + a_i$, then $a_n + a_i \mid a_k$ for some $k$, a contradiction. Therefore $3 \mid a_n + a_i$ for all $i$, so $a_1 \equiv a_2 \equiv \dots \equiv a_{n-1} \equiv -a_n (3)$. Thus if $3 \mid a_i$ for some $i$, then $3 \mid a_1, a_2 \dots, a_n$, so we can replace $a_i \to \frac{a_i}{3}$, therefore we can assume none of $a_1, a_2, \dots, a_n$ is divisible by $3$. Thus $3 \nmid a_{n-1} + a_{n-2}$, so if $a_{n-1} + a_{n-2} \mid 3a_k$, then $a_{n-1} + a_{n-2} \mid a_k$, which implies $k$ must be equal to $n$. So $a_{n-1} + a_{n-2} \le a_n$. Now applying induction hypothesis on the numbers $a_2, a_3, \dots, a_n$, there exists some $i$ and $j$ such that $a_i + a_j$ does not divide $3a_2, 3a_3, \dots, 3a_n$, therefore $a_i + a_j \mid 3a_1$. If none of $i, j$ is equal to $n$, then $3 \nmid a_i + a_j$, forces to $a_i + a_j \mid a_1$, a contradiction. Thus we can assume $j = n$. Hence $3a_1 < a_{n-1} + a_{n-2} + a_i \le a_n + a_i \le 3a_1$, which is an evident contradiction. $\blacksquare$

Assume for contradiction that this is false. WLOG assume ordering $a_1<a_2<\cdots<a_n$. De-scale the numbers so that they have no common factor. Suppose $a_n+a_i\mid 3a_j$. Note that if $3\nmid a_n+a_i$ then $a_n+a_i\mid a_j$, but then $a_n+a_i<a_j$, which is impossible. Hence, $3\mid a_n+a_i$ for each $1\leq i < n$. Since the numbers have no common factor, it follows that $3\mid a_i+a_j$ if and only if either $i=n$ or $j=n$. Assume that $a_{n-1}+a_i\mid a_k$ for $i < n-1$. This forces $k=n$. So, $L=\text{lcm}(a_{n-1}+a_1, a_{n-1}+a_2, \ldots, a_{n-1}+a_{n-2})\mid a_n$. Finally, note that we need $a_n+a_i\mid 3a_j$. Suppose $j<n$. Then, $a_n\leq 3a_j-a_i<2a_{n-1}$. But this is impossible as $a_n\geq L>2a_{n-1}$. So, $a_n+a_i\mid 3a_n$. But that means $a_n+a_i\mid 3a_i$, which means $a_n\leq 2a_i$. This is impossible as well as it again gives $a_n\mid 2a_{n-1}$. So, we have arrived at a contradiction. $\blacksquare$

hopefully not fakesolve Obviously use FTSOC. First optimize/use induction in two ways: If $a_n\mid a_{n-1}$ then by inductive hypothesis on $\{a_1,\dots,a_{n-1}\}$ we know that there exists $a_i+a_j$ not dividing any of $3a_1,\dots,3a_{n-1}$ and also $3a_n$. Thus assume $a_i\nmid a_j$ always. Also assume that $3\nmid a_i$ exists; otherwise we can just divide by $3$ until this holds. (bad at nt -> forgetting that assuming gcd 1 is a thing) Reorder as $a_1>\dots>a_n$. Then there exists $x$ and $y$ such that \[x(a_1+a_j)=3a_y\]for any $j\in \{2,\dots,n\}$ and yet obviously $x\in \{1,2\}$. Hence $a_1+a_j\equiv 0\pmod 3$. Now consider $a_2+a_3$, which is not a multiple of $3$. As a result it must divide one of $a_i$ and thus $a_1\ge a_i\ge a_2+a_3$. Now consider the set \[\{a_1+a_2,\dots,a_1+a_n\}.\]Any element of this set is equal to an element in the set \[\{3a_1,\dots,3a_n\}\cup \left\{\frac{3a_1}{2},\dots,\frac{3a_n}{2}\right\}.\]However if we have $a_1+a_j\mid \frac{3a_i}{2}$ and $i\ge 3$ then \[a_1+a_n\le \frac{3a_3}{2}\implies 2a_1<3a_3\implies 2a_2+2a_3<3a_3\implies 2a_2<a_3.\]which fails. Also notice that $3a_1$ is never reached; $3a_n$ cannot be reached either. Hence the set is actually \[\{3a_2,\dots,3a_{n-1}\}\cup \left\{\frac{3a_1}{2},\frac{3a_2}{2}\right\}.\]Now for some basic logic. If $\frac{3a_1}{2}=a_1+a_j$ then $a_1=2a_j$ which fails as $a_j\mid a_1$. However the set is now \[\{3a_2,\dots,3a_{n-1}\}\cup \left\{\frac{3a_2}{2}\right\}\]hence $3a_2=a_1+a_2$ is the largest element. Thus $a_1=2a_2$ and we fail again. $\blacksquare$ Remark: After getting modulo $3$ I should have easily finished with HamstPan's solution, oops. I think I knew something like that worked. idk why i didn't try it

why am i so bad at anti bonk

WLOG let $a_1 < a_2 < \dots < a_n$, and suppose that not all terms are divisible by $3$, otherwise just divide every term by $3$. If there exists $k < n$ such that $a_k + a_n \neq 0 \pmod 3$ then we are done, so suppose otherwise. Then $a_1 \equiv a_2 \equiv \dots \equiv a_{n-1} \not \equiv 0 \pmod 3$. Suppose that $a_{n-1} + a_{n-2}$ and $a_n + a_{n-1}$ both don't work. Then we get $a_{n-1} + a_{n-1} \leq a_n$ and $a_n + a_{n-1} \leq 3a_{n-2}$. Adding, we get $a_{n-1} \leq a_{n-2}$, contradiction.

Suppose $a_1<a_2<\dots a_n$, first consider $a_n+a_{n-1}$, if $a_{n-1}\neq \frac{a_n}{2}$ we get that $a_n+a_{n-1}\nmid 3a_n$ and as $2a_i<a_n+a_{n-1}$ for $i\neq n$, if $a_{n-1}=\frac{a_n}{2}$, consider $a_n+a_{n-2}$, we have that $a_{n-2}<a_{n-1}$ so $a_n+a_{n-2}\nmid 3a_n$ and $a_n+a_{n-2}\nmid \frac{3a_n}{2}$, thus as $2a_i<a_n+a_{n-1}$ for $i\neq n$ this works again.

Assume that $a_1 < a_2 < \dots < a_n$ and that their GCD is $1$ (the problem statement is homogenous). Suppose FTSOC that $a_i + a_j$ divides at least one of $3a_1, \dots, 3a_n$ for all $i$ and $j$. It must be that for all $i$, $a_i + a_n$ is either $\tfrac{3}{2} a_j$ or $3 a_j$ for some $j$; either way, a multiple of $3$. So, \[a_1 \equiv a_2 \equiv \dots \equiv a_{n-1} \equiv - a_n \pmod{3}.\]Since, by assumption, these numbers are not all multiples of $3$, it follows that $a_{n-2} + a_{n-1}$ is not a multiple of $3$, so it must divide $a_n$. But now, consider $a_{n-1} + a_n$: it is greater than $3a_j$ for all $j \leq n-1$, so it must divide $3a_n$. This implies that $a_{n-1} = \tfrac{a_n}{2}$, so $a_{n-2} = \tfrac{a_n}{2}$ as well, which contradicts the distinctness condition.

Suppose not. WLOG suppose $a_i \le a_{i+1}$ for all $i.$ Take $a_n,$ $a_{n-1}$ and $a_{n-2}$ and take $k=\min \{ v_3(a_n),v_3(a_{n-1}),v_3(a_{n-2}) \}.$ Take $b_i=\dfrac{a_i}{3^k}.$ Observe there must exist a sum of $b_n,b_{n-1},b_{n-2}$ that is not a multiple of $3.$ If this sum includes $b_n,$ we are done by size as $a_n$ and $a_{n-1}$ do not divide any $a_i$ and thus not $3a_i.$ Thus this sum must be $b_{n-2}+b_{n-1}.$ Observe then that $a_{n-2}+a_{n-1} \mid a_n$ so $a_{n-2}+a_{n-1} \le a_n.$ or all $a_{n-2} < \dfrac{1}{2}a_n.$ Take $a_{n}+a_{n-1} \ge 3a_i$ for $i \le {n-2}$ and observe that if $a_{n}+a_{n-1}$ is to divide $3a_n,$ then $2(a_{n}+a_{n-1})=3a_n,$ and similarly if it is to divide $3a_{n-1},$ then $a_{n}+a_{n-1}=3a_{n-1}$ so either way we have $a_n=2a_{n-1}.$ But then as $a_{n-2} < a_{n-1},$ $\dfrac{1}{2}a_n < a_{n-2}+a_{n-1} < a_n$ so $a_{n-2}+a_{n-1} \nmid a_n$ forming a contradiction, so we are done.

Churent wrote: An easier solution by induction: Key lemma: If $m > \frac{n}{2}$, then $m$ does not divide $n$. We proceed by induction on $n$, the number of distinct positive integers. Base case: $n=3$ WLOG let $a_1 < a_2 < a_3$. By our lemma, we know that $a_3 + a_2$ does not divide $3a_2$ or $3a_1$. Case i) $a_3 + a_2$ does not divide $3a_3$: Then we simply take $2, 3$ as the desired indices $i, j$ Case ii) $a_3 + a_2$ does divide $3a_3$: Since $\frac{3a_3}{3}<a_3 + a_2 <\frac{3a_3}{1}$, we must have that $a_3 + a_2 = 1.5a_3$ , or rather $a_3 = 2a_2$. Now consider $a_3 + a_1 = 2a_2 + a_1$. We know that $a_3 + a_1$ does not divide $a_1$ and $a_2$ by our key lemma. Furthermore, $$\frac{3a_3}{3} = 2a_2 < a_3 + a_1 = 2a_2 + a_1 < 3a_2 = \frac{3a_3}{2}$$. Thus $a_3 + a_1$ does not divide $a_3$ either, and we take $3, 1$ as our desired indices $i, j$. Inductive step: We shall assume the result is true for $n-1$ distinct positive integers. Thus note that for any $a_1 < a_2 < ... a_n$ we can find indices $2 \le i < j \le n$ such that $a_i + a_j$ does not divide any of $3a_2, 3a_3, ... 3a_n$ (by the inductive hypothesis). Furthermore, $a_i + a_j > 2a_1$, and once again by our key lemma $a_i + a_j$ does not divide $3a_1$ either, completing the inductive step. Might be 5 years late, but this solution seems wrong in the key lemma, as $m=n$ is possible. Is unfortunate that there is no good way to mark old solutions as wrong, as this one has 4 upvotes and might be causing fakesolves around the world to stay unnoticed.

Please contact westskigamer@gmail.com if there is an error with my solution for cash bounties by 3/18/2025.

Churent wrote: An easier solution by induction: Key lemma: If $m > \frac{n}{2}$, then $m$ does not divide $n$. We proceed by induction on $n$, the number of distinct positive integers. Base case: $n=3$ WLOG let $a_1 < a_2 < a_3$. By our lemma, we know that $a_3 + a_2$ does not divide $3a_2$ or $3a_1$. Case i) $a_3 + a_2$ does not divide $3a_3$: Then we simply take $2, 3$ as the desired indices $i, j$ Case ii) $a_3 + a_2$ does divide $3a_3$: Since $\frac{3a_3}{3}<a_3 + a_2 <\frac{3a_3}{1}$, we must have that $a_3 + a_2 = 1.5a_3$ , or rather $a_3 = 2a_2$. Now consider $a_3 + a_1 = 2a_2 + a_1$. We know that $a_3 + a_1$ does not divide $a_1$ and $a_2$ by our key lemma. Furthermore, $$\frac{3a_3}{3} = 2a_2 < a_3 + a_1 = 2a_2 + a_1 < 3a_2 = \frac{3a_3}{2}$$. Thus $a_3 + a_1$ does not divide $a_3$ either, and we take $3, 1$ as our desired indices $i, j$. Inductive step: We shall assume the result is true for $n-1$ distinct positive integers. Thus note that for any $a_1 < a_2 < ... a_n$ we can find indices $2 \le i < j \le n$ such that $a_i + a_j$ does not divide any of $3a_2, 3a_3, ... 3a_n$ (by the inductive hypothesis). Furthermore, $a_i + a_j > 2a_1$, and once again by our key lemma $a_i + a_j$ does not divide $3a_1$ either, completing the inductive step. Indeed, as noted in #38, please somebody somehow mark this solution as invalid.