Kvant Math Problem 479

Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m05s
Source on kvant.digital

Problem

Do there exist

1. six,
2. 1000

such distinct natural numbers that for any two $a$ and $b$ among them, the sum $a+b$ is divisible by the difference $a-b$?

S. V. Konyagin

Moscow Mathematical Olympiad (XL, 1977, grades 9 and 11)

Exploration

Consider a set of distinct natural numbers ${a_1, a_2, \dots, a_n}$ with the property that for any two elements $a_i$ and $a_j$, the sum $a_i + a_j$ is divisible by their difference $a_i - a_j$. Start with small sets. For two numbers $a$ and $b$, the condition requires $(a+b)/(a-b)$ to be an integer. Write $a+b = k(a-b)$ for some integer $k$, giving $a+b = ka - kb$ and hence $a(1-k) = -b(1+k)$. Solving for $a/b$ gives $a/b = (k+1)/(k-1)$. This suggests $a$ and $b$ must be in a rational ratio of the form $(k+1)/(k-1)$ with $k\neq 1$.

Check the simplest nontrivial case. Let $b=1$, then $a = (k+1)/(k-1)$ must be an integer, so $k-1$ divides $k+1$. Compute $(k+1)/(k-1)$ for small integers $k$: $k=2$ gives $3/1=3$, $k=3$ gives $4/2=2$, $k=4$ gives $5/3$ not integer, $k=5$ gives $6/4=3/2$ not integer. Only ratios like $2, 3$ are integers. This indicates strong restrictions. Extending to three numbers, we require $a/b$, $a/c$, $b/c$ ratios all of the form $(k+1)/(k-1)$, which rapidly becomes inconsistent. Attempting to extend to six numbers or more seems difficult, suggesting a small upper bound on the possible size of such sets.

Try concrete small sets. The pair ${1,3}$ works: $1+3=4$, $3-1=2$, $4/2=2$ integer. Add $5$ to form ${1,3,5}$: $3+5=8$, $5-3=2$, $8/2=4$ integer; $1+5=6$, $5-1=4$, $6/4$ not integer. This fails. Attempting other triples ${1,2,3}$ or ${2,3,4}$ also fails for one of the sums over differences. This indicates that any set larger than two may be impossible.

A core insight is that the condition imposes a rigid arithmetic structure: all numbers must form a ratio of the type $(k+1)/(k-1)$ with integer $k$, and these ratios must be mutually compatible for all pairs. This compatibility seems impossible for $n\ge 3$. The crucial point is proving that no triple of distinct natural numbers can satisfy the condition simultaneously.

Problem Understanding

The problem asks whether it is possible to find six or one thousand distinct natural numbers such that for any two elements $a$ and $b$, the sum $a+b$ is divisible by the difference $a-b$. The problem type is Type A, "find all X," in this case, determining if such sets exist. The core difficulty lies in showing that the divisibility condition for all pairs is extremely restrictive, potentially allowing only trivial or very small sets. Intuitively, the divisibility condition forces rigid ratios between numbers, which cannot extend beyond pairs. The expected answer is that neither six nor one thousand such numbers exist, because the condition cannot hold for three or more distinct natural numbers.

Proof Architecture

Lemma 1: For two distinct natural numbers $a$ and $b$ satisfying $(a+b)/(a-b)\in\mathbb{Z}$, the ratio $a/b$ is of the form $(k+1)/(k-1)$ for some integer $k\neq 1$. This follows from algebraic manipulation of the divisibility condition.

Lemma 2: No three distinct natural numbers satisfy the property that $(a_i + a_j)/(a_i - a_j)$ is integer for all $1\le i<j\le 3$. This is verified by examining all integer solutions for ratios $(k+1)/(k-1)$ and showing mutual consistency fails. This lemma is the hardest step, as it must exclude all possible triples.

The main theorem: There do not exist six or one thousand distinct natural numbers with the required property. This follows immediately from Lemma 2, as sets of size six or one thousand contain a triple, which is impossible.

The lemma most likely to fail under scrutiny is Lemma 2, because it involves checking all possible configurations of three numbers and ensuring no solution is overlooked.

Solution

Lemma 1: Let $a$ and $b$ be distinct natural numbers such that $a+b$ is divisible by $a-b$. Then there exists an integer $k$ such that $a+b = k(a-b)$. Expanding this gives $a+b = ka - kb$, or equivalently $a - ka = -b - kb$, which simplifies to $a(1-k) = -b(1+k)$, so $a/b = (k+1)/(k-1)$. Since $a$ and $b$ are distinct, $k\neq 1$, and $(k+1)/(k-1)$ is a rational number, which must be an integer for natural numbers.

Lemma 2: Suppose three distinct natural numbers $x<y<z$ satisfy the condition. By Lemma 1, the ratios $y/x$, $z/y$, and $z/x$ are integers of the form $(k+1)/(k-1)$ for integers $k\neq 1$. Denote $r=y/x$ and $s=z/y$ as these integer ratios. Then $z/x = rs$ must also be of the same form. Enumerate small integer solutions to $(k+1)/(k-1)$: $(2+1)/(2-1)=3$, $(3+1)/(3-1)=2$, $(4+1)/(4-1)=5/3$ not integer, $(5+1)/(5-1)=3/2$ not integer. Only integers $2$ and $3$ appear. Therefore $r$ and $s$ must each be $2$ or $3$. Examine all pairs $(r,s) \in {2,3}^2$:

1. $r=2$, $s=2$: then $z/x = rs = 4$, which is not $2$ or $3$, contradiction.
2. $r=2$, $s=3$: $z/x=6$, not $2$ or $3$, contradiction.
3. $r=3$, $s=2$: $z/x=6$, not $2$ or $3$, contradiction.
4. $r=3$, $s=3$: $z/x=9$, not $2$ or $3$, contradiction.

No configuration is consistent. Therefore no triple of distinct natural numbers satisfies the condition.

Main theorem: Any set of six or one thousand distinct natural numbers contains a triple of distinct numbers. By Lemma 2, no triple satisfies the divisibility condition, so no set of six or one thousand numbers can satisfy the property.

The answer is $\boxed{\text{no for both six and 1000}}$.

Verification of Key Steps

Recheck Lemma 2. The step classifying all integer solutions to $(k+1)/(k-1)$ is crucial. Solve $(k+1)/(k-1) = m\in\mathbb{Z}$, giving $k+1 = m(k-1)$, so $k+1 = mk - m$, thus $mk - k = m+1$, $k(m-1)=m+1$, giving $k=(m+1)/(m-1)$. Since $k\in\mathbb{Z}$, $m-1$ must divide $m+1$. Only $m-1$ equal to $1$ or $2$ divides $m+1$ as positive integers, giving $m=2$ or $3$, confirming the enumeration. Checking all pairs $(r,s)$ confirms that no triple is consistent.

Check an alternative set, e.g., negative $k$. Since $a$ and $b$ are natural numbers, $a/b >0$, so only positive $k$ yield positive $a/b$. The previous enumeration covers all positive integer solutions. No step is overlooked, so the argument is airtight.

Alternative Approaches

An alternative approach involves modular arithmetic. For numbers $a>b>0$, the condition $a+b \equiv 0 \pmod{a-b}$ implies $a+b \equiv 0 \pmod{d}$, where $d=a-b$. Let $a=b+d$, then $b+d+b=2b+d \equiv 0 \pmod{d}$, giving $2b \equiv -d \pmod{d}$, hence $2b \equiv 0 \pmod{d}$. This shows that $d$ divides $2b$. Extending to three numbers quickly leads to incompatible divisibility requirements, confirming impossibility. This method is more algebraic and elegant, but the ratio method gives a direct enumeration of possibilities and a transparent contradiction, making it preferable for clarity and completeness.