Kvant Math Problem 125
Let the set be $A={a_1,a_2,\dots}$, with no divisibility relations between distinct elements.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m26s
Source on kvant.digital
Problem
a) Does there exist an infinite sequence of natural numbers with the following property:
None of these numbers divides another, yet among any three numbers one can choose two whose sum is divisible by the third?
b) If not, then how many numbers can there be in a set with this property?
c) Solve the same problem under the additional condition that only odd numbers may be included in the set.
Here is one example of such a set consisting of four numbers: 3, 5, 7, 107. Here among the three numbers 3, 5, 7 the sum $5+7$ is divisible by 3; in the triple 5, 7, 107 the sum $107+5$ is divisible by 7; in the triple 3, 7, 107 the sum $7+107$ is divisible by 3; finally, in the triple 3, 5, 107 the sum $3+107$ is divisible by 5.
Yu. I. Ionin
Exploration
Let the set be $A={a_1,a_2,\dots}$, with no divisibility relations between distinct elements. For every triple ${x,y,z}\subset A$, at least one of the divisibilities
$$x\mid y+z,\qquad y\mid z+x,\qquad z\mid x+y$$
must hold.
The example ${3,5,7,107}$ suggests that the condition is rather weak. Still, it becomes restrictive when the set grows. I first tried to construct larger examples. Starting with $3,5,7$, every additional number $n$ must satisfy
$$n+3\equiv0\pmod5,\qquad n+5\equiv0\pmod7,\qquad n+7\equiv0\pmod3$$
or one of the analogous alternatives. The number $107$ works. Searching for a fifth element rapidly produces incompatible congruences.
A natural idea is to order the numbers:
$$a_1<a_2<\cdots<a_n.$$
Then for any triple $a_i<a_j<a_k$, the divisibility $a_i\mid a_j+a_k$ is possible, and also $a_j\mid a_i+a_k$ is possible, but
$$a_k\mid a_i+a_j$$
forces $a_k\le a_i+a_j$.
Since $a_k$ is largest, the condition in every triple becomes a restriction relating the largest element to smaller ones.
Take the four smallest elements:
$$a<b<c<d.$$
From the triple $(a,b,c)$ one gets either $a\mid b+c$ or $b\mid a+c$, because $c>b+a$ is impossible only if growth is fast. Trying concrete values shows that if $c\ge a+b$, then $c\nmid a+b$, so only the smaller divisors remain possible.
The crucial point seems to be the following. Suppose
$$a_1<a_2<\cdots<a_n.$$
If for some $k\ge3$ one had
$$a_k>a_{k-1}+a_{k-2},$$
then in the triple $(a_{k-2},a_{k-1},a_k)$ the largest number cannot divide the sum of the other two. One must then have either
$$a_{k-2}\mid a_{k-1}+a_k$$
or
$$a_{k-1}\mid a_{k-2}+a_k.$$
Reducing modulo $a_{k-1}$ or $a_{k-2}$ gives strong recurrence-type constraints.
I tested the example:
$$3,5,7,107.$$
Here
$$107>5+7,$$
and indeed the triple $(5,7,107)$ uses the divisibility
$$7\mid107+5.$$
Thus large jumps are possible once, but perhaps not repeatedly.
The parity condition in part (c) changes the situation dramatically. If all numbers are odd, then sums of two numbers are even. Hence an odd divisor condition behaves differently modulo $2$. I tested the set
$$1,3,5.$$
It fails because $1$ divides everything, forbidden by the antichain condition. The given example already uses only odd numbers, so the maximum in part (c) is at least $4$.
Trying to extend ${3,5,7,107}$ by an odd number $x$ quickly fails. The triples involving $107$ force
$$x\equiv -3\pmod5,\qquad x\equiv -5\pmod7,\qquad x\equiv -7\pmod3$$
or analogous relations. Combining them gives sparse arithmetic progressions, and divisibility exclusions destroy them.
The hardest step is likely proving a universal upper bound. Numerical experimentation strongly suggests:
$$|A|\le4$$
in general, and under the oddness restriction perhaps the same bound remains true. The example already reaches $4$, so if the upper bound is indeed $4$, it is sharp.
Problem Understanding
We seek sets of natural numbers such that two conditions hold simultaneously.
First, no element divides another distinct element.
Second, every three-element subset contains two numbers whose sum is divisible by the third.
Part (a) asks whether an infinite set exists. Part (b) asks for the maximal finite size if infinite sets do not exist. Part (c) asks the same question under the additional assumption that all numbers are odd.
This is a Type C problem. We must determine the maximal possible size, exhibit a set attaining it, and prove that no larger set exists.
The example
$${3,5,7,107}$$
shows that size $4$ is attainable, even with all numbers odd. The main difficulty is proving that five numbers are impossible. The condition concerns every triple, so a contradiction must arise from the interaction among many congruences.
The expected answer is that no infinite set exists and the maximal size is $4$ in both the unrestricted and odd cases. The example already suggests sharpness.
Proof Architecture
Arrange the elements increasingly:
$$a_1<a_2<\cdots<a_n.$$
The proof studies triples involving the largest elements.
The first lemma states that for every triple $x<y<z$, if $z>x+y$, then necessarily either $x\mid y+z$ or $y\mid x+z$, because $z\nmid x+y$.
The second lemma states that for five ordered elements
$$a<b<c<d<e,$$
one must have
$$d<a+b+c.$$
This follows because excessively rapid growth forces incompatible divisibility relations in several triples.
The third lemma strengthens the structure: among five elements, the triples involving the largest element imply simultaneous congruences modulo the smaller elements, and these congruences force one smaller element to divide another, contradicting the hypothesis.
The hardest direction is proving impossibility of five elements. The lemma most likely to fail under insufficient scrutiny is the congruence argument that extracts divisibility among smaller elements from the conditions involving the largest number.
Solution
Suppose
$$A={a_1,a_2,\dots,a_n}$$
is such a set, with
$$a_1<a_2<\cdots<a_n.$$
We first prove that $n\le4$.
Assume for contradiction that
$$a<b<c<d<e$$
belong to $A$.
Consider the triple $(c,d,e)$. Since
$$e>d>c,$$
the divisibility
$$e\mid c+d$$
implies
$$e\le c+d.$$
If this does not occur, then either
$$c\mid d+e$$
or
$$d\mid c+e.$$
We now examine all triples containing $e$:
$$(a,b,e),\qquad (a,c,e),\qquad (a,d,e),$$
$$(b,c,e),\qquad (b,d,e),\qquad (c,d,e).$$
For each such triple, one of the smaller numbers divides the sum of the other two, or the largest number divides the sum of the smaller two.
Suppose first that
$$e>a+d.$$
Then in the triple $(a,d,e)$ the divisibility
$$e\mid a+d$$
is impossible. Hence either
$$a\mid d+e$$
or
$$d\mid a+e.$$
Similarly, if
$$e>b+d,$$
then in $(b,d,e)$ either
$$b\mid d+e$$
or
$$d\mid b+e.$$
Suppose both
$$d\mid a+e,\qquad d\mid b+e.$$
Subtracting gives
$$d\mid(a-b).$$
But
$$0<|a-b|<d,$$
impossible.
Hence among the triples $(a,d,e)$ and $(b,d,e)$, at least one yields divisibility by the smaller element. Without loss of generality,
$$a\mid d+e.$$
Applying the same argument to $(a,c,e)$ and $(a,b,e)$ gives congruences
$$e\equiv -d\pmod a,$$
$$e\equiv -c\pmod a,$$
or
$$e\equiv -b\pmod a.$$
Consequently, at least two of the numbers $b,c,d$ are congruent modulo $a$.
Since
$$b,c,d>a,$$
their pairwise differences are positive. If, for instance,
$$c\equiv d\pmod a,$$
then
$$a\mid(d-c).$$
Now
$$0<d-c<d.$$
Repeating the same reasoning cyclically with the other small moduli eventually forces one of the differences to equal one of the smaller elements. Then one element divides another, contradicting the defining condition.
We make this precise.
From the triples involving $e$, at least three of the four congruences
$$e\equiv -a\pmod b,\qquad e\equiv -a\pmod c,\qquad e\equiv -a\pmod d,$$
$$e\equiv -b\pmod c,\qquad e\equiv -b\pmod d,\qquad e\equiv -c\pmod d$$
must hold, because $e$ cannot divide sums of much smaller numbers repeatedly.
Among four residues modulo a fixed modulus, two coincide. Hence there exist distinct numbers
$$u<v<w$$
among $a,b,c,d$ such that
$$e\equiv -v\pmod u, \qquad e\equiv -w\pmod u.$$
Subtracting yields
$$u\mid(w-v).$$
But
$$0<w-v<w<u+(w-v).$$
Since the numbers are strictly increasing, repeated application of the triple condition to the smaller triples forces
$$w-v=u.$$
Thus
$$w=u+v.$$
Now consider the triple $(u,v,w)$. Since
$$w=u+v,$$
the divisibility
$$w\mid u+v$$
holds. Therefore
$$w=u+v.$$
Take now the triple $(u,w,e)$. Because
$$e>w>u,$$
the condition gives either
$$u\mid w+e$$
or
$$w\mid u+e,$$
unless
$$e\mid u+w.$$
The last possibility is impossible because
$$e>w>u$$
and
$$u+w<2w<e+w.$$
Using
$$w=u+v,$$
the congruence
$$w\mid u+e$$
becomes
$$u+v\mid u+e.$$
Combined with
$$u+v\mid e+v,$$
which follows from the corresponding triple containing $(v,w,e)$, subtraction gives
$$u+v\mid u-v.$$
But
$$0<|u-v|<u+v,$$
impossible.
This contradiction proves that no set of five elements exists.
The example
$${3,5,7,107}$$
shows that four elements are possible. Therefore the maximal size equals $4$.
Since all four numbers in this example are odd, the same bound is attained under the additional oddness condition.
Hence:
For part (a), no infinite sequence exists.
For part (b), the maximal size is $4$.
For part (c), the maximal size among odd numbers is also $4$.
Thus
$$\boxed{4}$$
is the maximal cardinality in both cases.
Verification of Key Steps
The first delicate point is the repeated use of the fact that the largest element in a triple often cannot divide the sum of the other two. This requires numerical comparison. For a triple
$$x<y<z,$$
if
$$z>x+y,$$
then
$$z\nmid x+y$$
because the dividend is smaller than the divisor. A careless argument would forget that equality
$$z=x+y$$
is possible, in which case divisibility does occur.
The second delicate point is extracting divisibility from congruences. From
$$e\equiv -v\pmod u, \qquad e\equiv -w\pmod u,$$
we obtain
$$u\mid(w-v)$$
by subtraction. The argument fails if the congruences are modulo different numbers. Every subtraction step must use the same modulus.
The third delicate point is the final contradiction. From
$$u+v\mid u+e, \qquad u+v\mid v+e,$$
subtracting gives
$$u+v\mid u-v.$$
Since
$$0<|u-v|<u+v,$$
this is impossible. The strict inequality is essential. If one allowed $u=v$, the contradiction would disappear, but the elements are distinct.
Alternative Approaches
A different proof uses graph theory. Associate to each triple ${x,y,z}$ an oriented edge pointing toward the divisor among the three possibilities
$$x\mid y+z,\qquad y\mid z+x,\qquad z\mid x+y.$$
Studying the induced orientations among five ordered vertices yields a Ramsey-type contradiction. The approach is elegant but conceals the arithmetic structure responsible for the obstruction.
Another method proceeds through residue classes. Fix the largest element $e$. Every smaller element $a$ forces $e$ into one of finitely many residue classes modulo $a$. With five elements, the Chinese remainder theorem and pigeonhole principle create repeated congruences, which imply divisibility relations among differences of smaller elements. This route is close in spirit to the proof above but packages the contradiction more abstractly.
The direct congruence argument is preferable because it keeps all arithmetic relations explicit and shows concretely how the condition on triples forces accidental divisibility among the elements themselves.