Ionin Yu.I.

a) Does there exist an infinite sequence of natural numbers with the following property: no number in the sequence divides another, but among any three numbers, one can choose two whose sum is divisible by the third?

b) If not, how many numbers can be in a set with such a property?

c) Solve the same problem under the additional condition: only odd numbers are allowed in the set. Here is an example of such a set of four numbers: \(3, 5, 7, 107\). In the triplet \(3, 5, 7\), the sum \(5 + 7\) is divisible by 3; in the triplet \(5, 7, 107\), the sum \(107 + 5\) is divisible by 7; in the triplet \(3, 7, 107\), the sum \(7 + 107\) is divisible by 3; finally, in the triplet \(3, 5, 107\), the sum \(3 + 107\) is divisible by 5.
b) To the sequence of four numbers $3,5,7,107$ given in the condition, we can add the fifth number 10693: 10693 + 5 is divisible by $3,10693+3$ is divisible by $7,10693+7$ is divisible by $5,10693+107$ is divisible by 3 and by $5,10693+7$ is divisible by 107.

We will show that it is impossible to form a sequence satisfying the condition of the problem from six odd numbers. Let $a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}$ be such numbers. We will make several preliminary remarks.

1) If $a, b, c$ are three terms of our sequence, $a>b>c$, then $b+c$ does not divide $a$.

Indeed, if $b+c$ divided $a$, then $a$ would be equal to $b+c$, which contradicts the condition $a>b>c$.

2) If $a, b, c$ are three terms of our sequence, $a>b>c$, then $a+b$ is divisible by all terms of the sequence less than $b$, except possibly one.

Indeed, if $a+b$ is not divisible by two numbers $c$ and $d$, less than $b$, then $a+c$ and $a+d$ are divisible by $b$, but then $c-d$ is divisible by $b$, which is impossible.

3) If $a, b, c, d$ are four terms of our sequence, $a+b$ and $a+c$ are divisible by $d$, then $b+c$ does not divide $d$.

Indeed, since $a+b$ and $a+c$ are divisible by $d$, then $2a+(b+c)$ is divisible by $d$, while $2a$ is not divisible by $d$ (since $d$ is an odd number and $a$ is not divisible by $d$).

Let $a_{1}>a_{2}>a_{3}$ be the three largest of the six numbers $a_{1}, a_{2}, \ldots, a_{6}$.

Each of the numbers $a_{1}+a_{2}, a_{1}+a_{3}, a_{2}+a_{3}$, according to 2), is divisible by at least two of the numbers $a_{4}, a_{5}, a_{6}$. At the same time, 3) shows that these numbers do not have a common divisor among the numbers $a_{4}, a_{5}, a_{6}$. Therefore, each of the numbers $a_{1}+a_{2}, a_{1}+a_{3}, a_{2}+a_{3}$ is divisible by two of the numbers $a_{4}, a_{5}, a_{6}$ and does not divide the third.

Suppose $a_{1}+a_{2}$ is divisible by $a_{4}$ and $a_{5}$ and does not divide $a_{6} ; a_{1}+a_{3}$ is divisible by $a_{4}$ and $a_{6}$ and does not divide $a_{5} ; a_{2}+a_{3}$ is divisible by $a_{5}$ and $a_{6}$ and does not divide $a_{4}$. Then the numbers $a_{1}+a_{5}$ and $a_{2}+a_{4}$ are divisible by $a_{3}$. Therefore, the number $\left(a_{1}+a_{2}\right)+\left(a_{4}+a_{5}\right)$ is also divisible by $a_{3}$.

At the same time, $a_{1}+a_{2}$ is divisible by three of the numbers $a_{3}, a_{4}, a_{5}, a_{6}$, and since $a_{1}+a_{2}$ does not divide $a_{6}$, then $a_{1}+a_{2}$ divides $a_{3}$, from which it follows that $a_{4}+a_{5}$ divides $a_{3}$. This contradicts 1).

Thus, a sequence of odd numbers with the property we are interested in can consist of no more than five numbers.

b) If the sequence consists only of even numbers, then, without violating the condition, we can divide them all by 2. We will therefore assume that there are odd numbers in the sequence. By the result of part c), there are no more than five of them. Remarks 1) - 3) are now valid under some additional assumptions.

In 1) we need to require that $a$ does not equal $b+c$; 2) is valid if the number $a$ does not equal the sum of any two members of the sequence, and 3) is valid if $d$ is an odd number.

If the members of the sequence $a, b, c$ are even, and $d$ is odd, then the numbers $a+d, b+d$ and $c+d$ do not divide $a$, $b$, or $c$. Therefore, the numbers $a+b, a+c$ and $b+c$ divide $d$, which contradicts 3).

Thus, there are no more than two even numbers in our sequence. Let them be two: $a$ and $b(a>b)$. Then the number $a+b$ divides all odd members of the sequence, and therefore the number $a$ is the largest in the sequence.

If the number $a$ does not equal the sum of any two members of the sequence, then, by discarding the number $b$, we obtain a sequence for which remarks 1), 2), 3) are valid without any restrictions. The solution to part c) shows that such a sequence has no more than five members, that is, the original sequence has no more than six numbers.

Suppose now that the number $a$ equals the sum of some two odd members of the sequence. If $c$ is the larger of these odd numbers, then $a=c+d$ where $d$ is the smaller odd number. If $d > a/2$, then $c > a/2$, and $a = c + d > a$, which is a contradiction. If $d \leq a/2$, then $c \leq a/2$, and $a = c + d \leq a$, which is also a contradiction.

Thus, in any case, there are no more than six numbers in our sequence.

Here is an example of a six-member sequence: $2,3,5,7,107,10693$.

Submit a comment