the sum of two arbitrary different numbers in the sequence is always coprime with the sum of three arbitrary different numbers

Solution 1:

For the record:

https://artofproblemsolving.com/community/c6h1441130p8200462

All Russian Math Olympiad...

Solution 2:

This is an extended comment and not a complete answer. It describes an idea which to me seems obviously relevant, and which I did not pursue in detail.

We could (attempt to) build such a sequence inductively, adding one integer at a time. That is we could start with $P_2=\{a_1,a_2\}$ and find a suitable $a_3$ to form $P_3=\{a_1,a_2,a_3\}$ that "works so far". In general, if $P_n=\{a_1,a_2,...,a_n\}$, find and add a suitable $a_{n+1}$ that makes $P_{n+1}=\{a_1,a_2,...,a_n,a_{n+1}\}$ work.

I tend to think of the $P_n$ consisting of prime numbers (though that perhaps need not be a requirement).

What are some conditions, restrictions in picking $a_{n+1}$? If $P_n$ has been defined, we could look at all pairs $(a,b)$ of elements of $P_n$, look at all prime divisors of $a+b$, and make sure that the new number $c=a_{n+1}$ that we pick is not divisible by any of these $p$. This seems like a requirement that is easy to satisfy, since we are never going to run out of big primes (new big ones, not divisible by the old ones).

Another requirement, which I think is more important, say $c=a_{n+1}$ is the new integer we want to pick and add to $P_n$, to obtain $P_{n+1}$, and say $a,b\in P_n$. For any prime $p$ that divides $a$ we want to make sure that $p$ does not divide $b+c$. (Note there is symmetry here, we may interchange $a$ and $b$.) So we want to rule out all $c$ with $kp=b+c$, $k\in\mathbb Z$. Thus, from the set of "currently available for picking" numbers, we want to remove the set $\{kp-b:k\in\mathbb Z\}$.

Here is an illustration, starting with $P_2=\{3,5\}$. Remove $\{1,4,7,10,13,...\}$, and also remove $\{2,7,12,17,...\}$. (Note we are removing two arithmetic progressions $3k-5$ and $5k-3$.) If (for presumed convenience and to stay out of unforeseen trouble) we stick to pick primes, the prime $7$ has been ruled out, but $11$ is available, so we take $P_3=\{3,5,11\}.$ (Picking primes allows for another simplification of the rule excluding new candidates, I think, but will not try to write it down.)

Now, the pair $(3,5)$ has already been taken care of (that is, we remember that we should never pick numbers $3k-5$ and $5k-3$). The pair $(3,11)$ tells us not to pick numbers $\{8,19,30,41,52,...\}$ or numbers $\{1,4,7,10,13,16,...\}$ (and the latter (co-)set was taken care of, already). The pair $(5,11)$ rules out numbers $\{6,17,28,39,50,...\}$ and $\{4,9,14,19,...\}$. In addition $3+11=14$ with a prime factor of 7, ruling out all multiples of $7$ as well (but this was the "easy" not to worry too much about, part of the ruling out process). It so happens that $3+5$ and $5+11$ are both powers of $2,$ but we have already ruled out even numbers since we read the comments.

The question, of course, could this process, this inductive picking of new numbers, go on forever? If we had included an even number in $P_2$ then the answer is no. What about $P_2=\{3,5\}$ or an even better (in what way) choice of $P_2$? Obviously the problem has something to do with arithmetic progressions, at every step we have excluded finitely many arithmetic progressions, do we reach a step when we covered all integers with finitely many arithmetic progressions? (That is, we ruled out all the integers and there is nothing that remains available to pick a new number from.) I believe this topic is well-researched, and someone could easily complete the solution, hopefully. (That is to say, I do not feel competent to do it myself, and I can't really tell what others could do :) (I tend to think of Hales–Jewett theorem, but didn't think hard enough to see if it is relevant.)

I just realized I was (implicitly) thinking of a restricted version of the problem, saying that if $a,b,c$ are members of the sequence then the sum of any two members of $\{a,b,c\}$ is coprime with $a+b+c$. I didn't think of the case when we pick four or five members of the sequence, say $a,b,c,d,e$, so I didn't think of the requirement (and variations thereof) that $a+b$ is coprime with $c+d+e$. So now I think the problem is more complicated, at least for me, than I had assumed earlier. This, on one hand, makes me feel it would be more difficult to show that such a sequence exists, on the other hand it seems that even for the full version of the problem one could express the set of excluded integers at each stage (i.e. at each inductive step) as the union of finitely many arithmetic progressions.