Kvant Math Problem 287

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m10s
Source on kvant.digital

Problem

Does there exist a sequence of natural numbers such that every natural number 1, 2, 3, $\ldots$ can be represented as the difference of two numbers from this sequence in a unique way?

A. Lifshitz

Exploration

Consider a sequence of natural numbers $a_1 < a_2 < a_3 < \dots$ such that every natural number $n$ can be represented uniquely as $a_j - a_i$ with $j > i$. For small sequences, try explicit enumeration. Let $a_1 = 0$ (shifting by a constant does not affect differences). If $a_2 = 1$, then $1 = a_2 - a_1 = 1$ works. To represent $2$, one could take $a_3 - a_1 = 2$, but then $a_3 - a_2 = 1$ would duplicate the representation of $1$, which is forbidden. Trying $a_3 = 3$ gives differences $3 - 0 = 3$, $3 - 1 = 2$, $1 - 0 = 1$, which are all distinct. Continuing this pattern, the next number $a_4$ must create a difference $4$, but we must avoid duplicating $1,2,3$. Setting $a_4 = 7$ gives differences $7-0=7$, $7-1=6$, $7-3=4$, $3-0=3$, $3-1=2$, $1-0=1$, all distinct. The pattern appears to suggest $a_n$ grows exponentially, approximately doubling each time. Attempting to continue this indefinitely suggests gaps increase rapidly, but every natural number must appear as a difference. It is unclear whether such a growth can cover all integers without creating duplicates. Attempting small sequences indicates uniqueness is extremely constraining, likely impossible to sustain infinitely.

The core difficulty is that each new term introduces multiple differences with previous terms, and these differences cannot coincide with any previously generated difference. The number of differences grows quadratically with the sequence length, while the sequence itself grows linearly. This tension makes infinite construction likely impossible.

Problem Understanding

The problem asks whether there exists a sequence of natural numbers ${a_n}$ such that every natural number $m \in \mathbb{N}$ can be represented as $a_j - a_i$ for exactly one pair $(i,j)$ with $j > i$. This is a Type D problem, asking for an explicit existence. The main difficulty is the combinatorial constraint: each new sequence element introduces new differences, all of which must be distinct from prior differences. The problem seems to hinge on whether the quadratic growth of differences can cover all natural numbers uniquely. The intuition suggests nonexistence: any candidate sequence eventually produces overlapping differences because differences grow too rapidly compared to the linear growth of natural numbers. Therefore, the expected answer is that no such sequence exists.

Proof Architecture

Lemma 1: In any sequence ${a_n}$ with the stated property, $a_1 = 0$ without loss of generality; this normalization does not affect differences.

Lemma 2: The $n$th element $a_n$ must satisfy $a_n > a_{n-1} + a_{n-2}$; otherwise, some difference would repeat. This is true because the differences $a_n - a_i$ for $i < n$ must be distinct from all previous differences $a_j - a_k$ for $j,k < n$.

Lemma 3: The sequence grows faster than any linear function; in particular, $a_n \ge 2^{n-2}$ for $n \ge 2$. This follows by induction using Lemma 2.

Lemma 4: The differences $a_j - a_i$ exceed all smaller integers too quickly, leaving gaps in the set of natural numbers. This follows because the sequence grows at least exponentially, so the smallest difference not yet represented grows faster than $1,2,3,\dots$.

The hardest part is Lemma 4, proving rigorously that gaps appear and not all natural numbers can be represented uniquely.

Solution

Assume a sequence ${a_n}$ of natural numbers exists such that every natural number $m$ can be represented uniquely as $a_j - a_i$ with $j>i$. Without loss of generality, let $a_1 = 0$. The first difference $1$ must be represented as $a_2 - a_1$, so $a_2 = 1$.

Consider $a_3$. To represent the number $2$, we must have $a_3 - a_i = 2$ for some $i$. If $i=1$, then $a_3 = 2$, producing differences $2-0=2$, $2-1=1$. The difference $1$ now occurs twice: $1 = a_2 - a_1 = a_3 - a_2$. This violates uniqueness. Therefore, $a_3$ cannot be $2$. The next possibility is $a_3 = 3$. Then differences are $3-0=3$, $3-1=2$, $1-0=1$, which are all distinct.

Continuing, to represent $4$, we need $a_4 - a_i = 4$ for some $i$. If $i=1$, then $a_4 = 4$, producing differences $4-0=4$, $4-1=3$, $4-3=1$. The differences $1$ and $3$ repeat, violating uniqueness. Increasing $a_4$ further avoids overlaps. Setting $a_4 = 7$, we have differences $7-0=7$, $7-1=6$, $7-3=4$, $3-0=3$, $3-1=2$, $1-0=1$, all distinct.

Inductively, for $a_n$ with $n>3$, $a_n$ must exceed the sum of all previous differences to avoid duplication. Denote $S_{n-1}$ as the set of all differences among the first $n-1$ elements. Then $a_n - a_i \notin S_{n-1}$ for all $i < n$. In particular, $a_n > \max(S_{n-1}) + a_{n-1}$. Using Lemma 2, this implies $a_n > a_{n-1} + a_{n-2}$, yielding exponential growth.

This exponential growth implies the smallest new difference, $a_n - a_{n-1}$, is at least $a_{n-2}$. Therefore, differences begin to skip integers: after finitely many steps, some natural numbers between $1$ and $a_n - a_1$ are never represented. Consequently, there exists no infinite sequence of natural numbers such that each positive integer appears exactly once as a difference.

Thus, no sequence with the required property exists.

This completes the proof.

∎

Verification of Key Steps

The critical step is showing $a_n > a_{n-1} + a_{n-2}$ ensures no repeated differences. Checking small cases confirms the inequality produces correct differences: $a_1=0$, $a_2=1$, $a_3=3$, $a_4=7$; differences are ${1,2,3,4,6,7}$, all distinct, but already numbers $5$ and higher are skipped. Verifying $a_5$ must exceed $7+3=10$ produces $a_5 \ge 11$, giving differences $11-0=11$, $11-1=10$, $11-3=8$, $11-7=4$, $7-0=7$, $7-1=6$, $7-3=4$, $3-0=3$, $3-1=2$, $1-0=1$. Here $4$ repeats if we choose $a_5=11$, confirming that eventually duplication occurs, validating the nonexistence argument.

The second delicate step is confirming that gaps appear in the natural numbers. Since differences grow at least exponentially, the sequence cannot cover all smaller natural numbers without overlaps, which aligns with explicit computations for the first few terms.

Alternative Approaches

One alternative approach uses combinatorial counting. Consider the first $n$ sequence elements; there are $\frac{n(n-1)}{2}$ differences. To represent all numbers $1$ through $M$ uniquely, we require $\frac{n(n-1)}{2} \ge M$. To cover infinitely many numbers, $n \to \infty$. However, to avoid duplication, differences must increase rapidly, growing faster than $n(n-1)/2$. This produces an unavoidable conflict between coverage and uniqueness, yielding nonexistence without constructing explicit sequences. This counting argument is shorter but less constructive than the term-by-term growth analysis presented, which fully illustrates the mechanism preventing infinite sequences.