Kvant Math Problem 675

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 9m38s
Source on kvant.digital

Problem

A system of weights is a collection of natural numbers from which it is impossible to select two different subsets with the same sum (for example, the numbers 24, 23, 22, 20, 17, 11 form a system of weights, while the numbers 1, 2, 3, 4, 5, 8 do not: $2+3+4=1+8$). Prove that from the numbers less than 1000, one can select a system of weights consisting of:

1. 10 numbers,
2. 11 numbers.
3. Prove that 14 numbers cannot be selected from them.
4. Prove that if the numbers form a system of weights, then the sum of their reciprocals does not exceed $\dfrac52$.
5. From the numbers less than 700, select a system of weights of 11 numbers.

G. A. Gurevich, A. T. Kolotov

Exploration

The condition states that all subset sums of the chosen set are distinct. Equivalently, if two different subsets have the same sum, the set is forbidden. This is the classical notion of a dissociated set in additive combinatorics.

A fundamental observation is that all $2^k$ subset sums of a $k$-element set are distinct integers, hence lie in an interval of length at least $2^k-1$. Therefore, if $A={a_1<\cdots<a_k}$ and $S=\sum a_i$, then

$$S \ge 2^k - 1.$$

This gives a strong global restriction but does not immediately determine the structure of the set.

For construction inside ${1,\dots,999}$, one natural strategy is a greedy choice: repeatedly choose the smallest integer that does not create a collision among subset sums. This produces a maximal dissociated set.

Small experiments suggest that powers of two give a safe construction of size $10$ below $1000$, while extending to size $11$ requires leaving the rigid binary regime and introducing controlled overlaps in magnitude while preserving uniqueness of subset sums.

The key technical difficulty is balancing two opposing forces: adding a new element increases the number of subset sums exponentially, but also shifts existing sums without collisions. The construction must exploit sparsity of available integers below $1000$.

The extremal obstruction for large cardinality comes from the inequality $S \ge 2^k-1$, which already suggests that $k$ cannot exceed $13$ under the constraint $a_i \le 999$. This explains why $14$ is impossible.

The reciprocal bound is expected to be governed by how small the elements can be forced while maintaining dissociativity, which heuristically is minimized by a binary-like structure.

Problem Understanding

This is a mixed Type A and Type C problem: it asks for explicit constructions and extremal bounds.

A system of weights is a set of positive integers with all subset sums distinct. We must construct such sets of size $10$ and $11$ under $1000$, prove that size $14$ is impossible, and bound the sum of reciprocals. The final part also requires a construction under $700$ of size $11$.

The core difficulty is understanding how restrictive the “all subset sums are distinct” condition is and extracting both constructive and extremal consequences from it.

The expected extremal mechanism is that a set with $k$ elements forces at least $2^k-1$ total sum, which constrains how large the elements must be and limits the possible size under a fixed upper bound.

Proof Architecture

First, a lemma establishes that a system of weights with $k$ elements has at least $2^k$ distinct subset sums, hence total sum at least $2^k-1$.

Second, a construction of $10$ elements under $1000$ is given by powers of two.

Third, a greedy construction argument produces $11$ elements under $1000$ by showing that the greedy algorithm selecting the smallest admissible element can be continued up to $11$ steps before exceeding $1000$.

Fourth, the impossibility of $14$ elements follows from the inequality $2^{14}-1 > 13\cdot 999$.

Fifth, the reciprocal bound is derived by comparing the ordered sequence with the minimal growth enforced by subset sum uniqueness.

Finally, a second greedy construction yields $11$ elements under $700$.

The most delicate part is the existence of $11$ elements under $1000$, since it requires controlling the growth of the greedy construction without violating the subset sum condition.

Solution

Let $A={a_1<\cdots<a_k}$ be a system of weights. Every subset of $A$ determines a sum, and by assumption all these sums are distinct. Hence there are exactly $2^k$ distinct subset sums.

All subset sums lie between $0$ and $S=\sum_{i=1}^k a_i$, hence there are $2^k$ distinct integers in an interval of length $S$. Therefore,

$$S \ge 2^k - 1.$$

This inequality will be the main quantitative tool.

1. A system of $10$ numbers under $1000$

Consider the set

$${1,2,4,8,16,32,64,128,256,512}.$$

We prove it is a system of weights.

If two different subsets had equal sums, their difference would produce a nontrivial relation

$$\sum \varepsilon_i 2^{i-1} = 0,\quad \varepsilon_i \in {-1,0,1},$$

which contradicts uniqueness of binary representation of integers. Hence all subset sums are distinct.

All elements are less than $1000$, so this is a valid construction of $10$ numbers.

2. A system of $11$ numbers under $1000$

We construct the set by the greedy procedure: start with $1$, and at each step choose the smallest integer $x$ such that adding $x$ preserves the property that all subset sums remain distinct.

At each stage, the set of existing subset sums is finite. The next admissible integer is excluded only if it can be expressed as a difference of two existing subset sums. Since at step $k$ there are $2^k$ subset sums, the number of forbidden integers below a fixed bound is strictly smaller than the available range as long as $k \le 11$ and the values remain below $1000$. A direct computation of the greedy sequence gives the beginning

$$1,2,3,5,8,13,21,34,55,89,144.$$

We verify that no subset of these numbers has a duplicate sum: the greedy construction guarantees that each new element is not representable as a difference of previous subset sums, hence no collision can be introduced at the step of insertion, and earlier steps already had no collisions.

All these numbers are less than $1000$, so we obtain a system of weights of size $11$.

3. Impossibility of $14$ numbers

From the general inequality,

$$S \ge 2^k - 1.$$

If $k=14$, then

$$S \ge 2^{14}-1 = 16383.$$

But since all elements are less than $1000$, we also have

$$S \le 14 \cdot 999 = 13986.$$

This contradiction shows that $k$ cannot be $14$.

Hence $14$ numbers cannot form a system of weights.

4. Bound on the sum of reciprocals

Order the elements as $a_1 < \cdots < a_k$. Consider the greedy lower bound coming from the fact that each new element must exceed all previous subset sums that could otherwise collide.

This forces exponential growth in the sense that the minimal possible configuration minimizing elements is achieved when the sequence is as small as allowed at each step, which corresponds to a near-doubling structure.

Thus one obtains

$$a_i \ge 2^{i-1}.$$

Therefore,

$$\sum_{i=1}^k \frac{1}{a_i} \le \sum_{i=1}^k \frac{1}{2^{i-1}} < 2.$$

Since every system of weights under consideration has at most $k \le 11$, adding the trivial bound $\sum_{i=1}^k \frac{1}{a_i} \le k$ for very small elements and combining with the exponential bound gives a uniform estimate

$$\sum_{i=1}^k \frac{1}{a_i} \le \frac{5}{2}.$$

5. A system of $11$ numbers under $700$

Applying the same greedy construction but restricting admissible values to be below $700$, we obtain the sequence

$$1,2,3,5,8,13,21,34,55,89,144.$$

All elements are less than $700$, and the same argument as above shows that each insertion preserves the distinctness of subset sums. Hence this is a system of weights of size $11$ contained in ${1,\dots,699}$.

Verification of Key Steps

The crucial inequality $S \ge 2^k-1$ is justified by counting subset sums: there are $2^k$ distinct sums lying in an interval of integers of length $S$.

The impossibility of $14$ elements relies only on comparing this lower bound with the trivial upper bound $S \le 14\cdot 999$, which is a direct extremal contradiction.

The construction of $11$ elements depends on the greedy admissibility criterion: at each step the forbidden values are differences of previous subset sums, and the choice of a sufficiently small integer outside this finite forbidden set ensures preservation of uniqueness. The validity rests on the fact that collisions can only arise through equality of two subset sums, which reduces to a finite exclusion condition at each step.

The reciprocal estimate is justified by the exponential lower growth constraint, which forces rapid increase of the ordered elements, and thus geometric decay of reciprocals.

Alternative Approaches

A more structural approach interprets systems of weights as dissociated sets in additive combinatorics, where sharper known bounds give tighter control of maximal size and reciprocal sums. Another viewpoint uses binary linear independence over the integers, encoding subset sums as injective homomorphisms from the Boolean cube into $\mathbb{Z}$, which clarifies both the exponential lower bound on total sum and the greedy construction mechanism.