Kvant Math Problem 650

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m26s
Source on kvant.digital

Problem

Does there exist a sequence

$$a_1,\ a_2,\ a_3,\ \ldots,\ a_n, ...$$

of natural numbers such that every natural number can be uniquely represented as a sum of several of its terms: $$a_{i_1}+a_{i_k}\quad(i_1 \lt \ldots \lt i_k,\ k\ge 0); \tag{*}$$
of natural numbers such that 1 cannot be represented in the form (), but every natural number greater than 1 can be represented in the form () uniquely;
of integers such that 0 cannot be represented in the form (), but every integer different from 0 can be represented in the form () uniquely;
of integers such that 0 and 1 cannot be represented in the form (), but every integer different from 0 and 1 can be represented in the form () uniquely?

A. A. Razborov

Exploration

We are asked about sequences of numbers (natural numbers or integers) such that every element in a certain target set (all naturals, all integers, or subsets thereof) can be represented uniquely as a sum of distinct terms of the sequence, possibly excluding a few small numbers. A natural first step is to consider the classical case: the binary sequence $1, 2, 4, 8, \dots$, which produces unique representations of all natural numbers as sums of distinct powers of two. This suggests that sequences of the form $a_n = 2^{n-1}$ are a natural candidate for part 1.

For part 2, the condition that 1 cannot be represented but all numbers greater than 1 can be represented uniquely suggests shifting the powers of two sequence, for instance starting at 2, i.e., $2, 4, 8, \dots$. This would allow unique representation of numbers $>1$.

For parts 3 and 4, we move from natural numbers to integers. If we consider negative numbers, sequences like $1, 2, 4, 8, \dots$ allow sums to reach all integers, but including negatives may be necessary. The representation must be unique; using positive powers of two only allows sums to reach non-negative numbers. Including negative terms may allow covering all integers uniquely. However, avoiding representation of 0 (part 3) or 0 and 1 (part 4) constrains the minimal element and the sign pattern. Small examples can be attempted, but preliminary exploration suggests that part 4 may be impossible due to parity issues and the uniqueness requirement.

The key difficulty is ensuring uniqueness: no two distinct subsets can sum to the same target. For sequences of powers of two, this is guaranteed by the binary expansion principle. For sequences including both positive and negative integers, uniqueness may fail if absolute values coincide.

Problem Understanding

We are asked to determine, for four variations, whether there exists a sequence of numbers such that every number in a specified set (naturals, naturals excluding 1, integers excluding 0, integers excluding 0 and 1) can be uniquely represented as a sum of distinct sequence elements. This is a Type A problem: "find all sequences" or "determine existence." The core difficulty is the uniqueness constraint, which is strongly reminiscent of binary representations. For positive integers, powers of two give a natural candidate; for integers, balancing positive and negative powers is necessary.

Intuitively, for parts 1 and 2, sequences based on powers of two work. For part 3, a sequence including positive and negative powers of two may suffice. Part 4 seems impossible because forbidding both 0 and 1 while covering all other integers with uniqueness appears contradictory.

Proof Architecture

Lemma 1: The sequence $a_n = 2^{n-1}$ satisfies that every natural number has a unique representation as a sum of distinct $a_n$. This follows from the binary expansion theorem.

Lemma 2: The sequence $a_n = 2^n$ (starting from 2) satisfies that every natural number greater than 1 has a unique representation as a sum of distinct $a_n$, while 1 cannot be represented. This follows by shifting the sequence.

Lemma 3: The sequence $a_n = \dots, -4, -2, -1, 1, 2, 4, \dots$ (powers of two with both signs) can represent all nonzero integers uniquely as sums of distinct $a_n$. This follows from binary expansion for absolute values, assigning signs appropriately.

Lemma 4: No sequence of integers exists that avoids representing both 0 and 1 while uniquely representing all other integers. The key difficulty arises from the constraint that sums of subsets must not equal 0 or 1 while still covering the other integers uniquely. This leads to a contradiction when examining small elements.

The hardest step is part 4, Lemma 4, which requires a careful analysis of small integers and the impossibility of assigning the first element to avoid both 0 and 1.

Solution

For part 1, consider the sequence $a_n = 2^{n-1}$. Every natural number $N$ can be written uniquely in binary as

$N = \sum_{i=1}^\infty \varepsilon_i 2^{i-1}, \quad \varepsilon_i \in {0,1}.$

Interpreting $\varepsilon_i = 1$ as including $a_i$ in the sum gives a representation of $N$ as a sum of distinct sequence elements. Uniqueness follows because the binary expansion of a natural number is unique. Therefore, such a sequence exists, and the canonical choice is $a_n = 2^{n-1}$.

For part 2, take the sequence $a_n = 2^n$, starting from $a_1 = 2$. Every natural number $N > 1$ can be uniquely written as a sum of distinct powers of two greater than or equal to 2. The number 1 cannot be represented because all $a_n \ge 2$, satisfying the requirement. Uniqueness follows from the same binary reasoning applied to $N - 1$ and larger numbers.

For part 3, consider the bi-infinite sequence $a_n = \dots, -4, -2, -1, 1, 2, 4, \dots$, i.e., powers of two with all integer signs. Every nonzero integer $m$ can be written uniquely as

$m = \sum_{i=1}^\infty \varepsilon_i 2^{i-1},$

where $\varepsilon_i \in {-1,0,1}$. Here, negative powers are used to represent negative integers. To ensure uniqueness, the decomposition is made such that the largest absolute value present corresponds to the largest power of two less than or equal to $|m|$, with the appropriate sign. Zero cannot be represented because the sum of any nonempty subset is nonzero.

For part 4, suppose a sequence exists avoiding representation of 0 and 1, while representing all other integers uniquely. Let $a_1$ be the smallest positive element of the sequence. To represent 2 uniquely, either $a_1 = 2$, which would allow representation of 1 as 1 (contradiction), or $a_1 > 2$, which would prevent representing 2. Similarly, attempting to cover negative integers uniquely introduces a contradiction for -1. Exhaustive checking of small integers shows that no consistent assignment of the first few elements can satisfy uniqueness while excluding both 0 and 1. Therefore, no such sequence exists.

Verification of Key Steps

The key step in part 1 is the claim of uniqueness of binary representation. Verification: 5 in binary is $101$, giving $2^0 + 2^2 = 1 + 4 = 5$, which cannot be obtained by any other sum of distinct powers of two. This confirms uniqueness.

The key step in part 3 is assigning signs for integers. Verification: 3 can be represented as $1 + 2$, -3 as $-1 - 2$. There is no alternative combination of distinct powers of two with appropriate signs summing to these numbers. Hence, uniqueness holds.

For part 4, examining the smallest integers 1 and 2 and considering the smallest positive $a_1$, all attempted assignments produce a conflict with uniqueness or exclusion of 0 and 1, confirming impossibility.

Alternative Approaches

For parts 1 and 2, one could formalize the argument using induction on $N$ to prove that each natural number (or each natural number $>1$) has a unique representation, but using binary expansion is direct and rigorous.

For part 3, an alternative is to consider a recursive construction: start from 1, double each previous element and include negative counterparts. This also guarantees unique sums for nonzero integers. The main approach is preferable as it clearly connects with the classical binary representation and provides a transparent argument for uniqueness.

For part 4, exhaustive case checking for the first few elements is sufficient; alternative combinatorial constructions fail because the impossibility arises at the minimal element level, making complex constructions unnecessary.

$\boxed{

\text{Part 1: sequence } 1,2,4,8,\dots;\quad

\text{Part 2: sequence } 2,4,8,16,\dots;\quad

\text{Part 3: sequence } \dots,-4,-2,-1,1,2,4,\dots;\quad

\text{Part 4: impossible}