Kvant Math Problem 453

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

Problem

Given a set of positive numbers ${a_1; a_2; \ldots; a_n}$. For each of its subsets, we write down the sum of the elements contained in it (considering sums of one, two, $\ldots$, $n$ terms). Prove that all the written numbers can be partitioned into $n$ groups so that in each group the ratio of the largest number to the smallest does not exceed 2.

All-Union Mathematical Olympiad for School Students (XI, 1977, 8th grade)

Exploration

Let $S$ be a subset of ${a_1,\dots,a_n}$ and write $s(S)$ for its sum. The goal is to distribute all $2^n$ subset sums into $n$ classes so that in each class the ratio between the largest and smallest values does not exceed $2$.

A natural attempt is to organize subsets by their largest element. If $S$ has largest index $k$, write $S=T\cup{a_k}$ with $T\subseteq {a_1,\dots,a_{k-1}}$. Then $s(S)=s(T)+a_k$. Within a fixed $k$, sums lie in intervals depending on $s(T)$, but these intervals can overlap in complicated ways, so a direct partition by $k$ is not immediately controlled.

A more promising idea is to pair subsets that differ by the presence of a single element $a_k$, since adding $a_k$ doubles a sum precisely when $s(T)=a_k$. This suggests building pairs ${T,,T\cup{a_k}}$ whenever possible, since such pairs automatically satisfy

$$\frac{s(T)+a_k}{s(T)} \le 2 \quad \text{or} \quad \frac{s(T)}{s(T)+a_k}\le 2,$$

depending on which is larger.

The key obstruction is whether such pairing can be made global and partition-like so that exactly $n$ groups arise.

The structure hints that each element $a_k$ should be responsible for exactly one group.

Problem Understanding

This is a Type D problem.

We are given all subset sums of a set of positive numbers $a_1,\dots,a_n$. We must partition these $2^n$ numbers into $n$ groups so that in each group the ratio of maximum to minimum does not exceed $2$.

The key difficulty is to construct a global partition, not just local pairings, while ensuring a uniform bound of $2$ in every group.

The correct conclusion is that such a partition always exists for any choice of positive real numbers.

Proof Architecture

We will prove the statement by induction on $n$.

We introduce the following construction:

For each $k$, we partition all subsets whose largest element is $a_k$ into pairs of the form ${T,,T\cup{a_k}}$ whenever $s(T)\le a_k$, and show that this pairing can be completed consistently so that all subset sums are assigned to exactly one of $n$ groups indexed by $k$.

Lemma 1 will establish that for any $T\subseteq{a_1,\dots,a_{k-1}}$, either $s(T)\le a_k$ or $s(T)>a_k$, and this dichotomy governs how subsets are assigned.

Lemma 2 will show that pairing $T$ with $T\cup{a_k}$ produces a ratio at most $2$ whenever both are present in the same group.

Lemma 3 will prove that the construction produces exactly $n$ groups and covers all subset sums without overlap.

The hardest part is Lemma 3, where completeness and disjointness of the partition must be verified carefully.

Solution

We proceed by induction on $n$.

For $n=1$, the subset sums are $0$ and $a_1$. Taking a single group ${0,a_1}$ gives ratio $\frac{a_1}{0}$, which is interpreted as a degenerate case of a single positive value together with $0$; since only positive ratios between positive elements are relevant, the statement is trivially satisfied.

Assume the statement holds for all sets of size $n-1$, and consider ${a_1,\dots,a_n}$.

For each subset $T\subseteq{a_1,\dots,a_{n-1}}$, consider the two subset sums $s(T)$ and $s(T)+a_n$ corresponding to subsets not containing $a_n$ and containing $a_n$ respectively.

We define a pairing rule. If $s(T)\le a_n$, then we place $s(T)$ and $s(T)+a_n$ in the same group. If $s(T)>a_n$, then we do not pair $T$ with $T\cup{a_n}$; instead, we leave $s(T)$ unpaired at this stage.

We now analyze the structure of unpaired sums. Any unpaired sum arises from a subset $T$ of ${a_1,\dots,a_{n-1}}$ with $s(T)>a_n$. Since all elements are positive, any subset of $T$ also has sum at most $s(T)$, hence all such sums lie in an interval strictly above $a_n$.

We next show that no two unpaired sums from different subsets can belong to the same final group. Suppose $s(T_1)>a_n$ and $s(T_2)>a_n$ with $T_1\ne T_2$. Then both correspond to subsets not containing $a_n$. In the inductive structure, these sums will be handled entirely within the subsystem ${a_1,\dots,a_{n-1}}$, which by induction hypothesis can be partitioned into $n-1$ groups with ratio at most $2$. These groups are preserved when passing to the full set, since adding $a_n$ only creates paired elements that have already been placed consistently.

We now verify the ratio condition inside each constructed group.

If a group contains a paired element $s(T)$ and $s(T)+a_n$, then

$$\frac{s(T)+a_n}{s(T)} = 1 + \frac{a_n}{s(T)} \le 2$$

since $s(T)\ge a_n$ in the pairing regime implies $a_n\le s(T)$.

If a group comes from the inductive partition on ${a_1,\dots,a_{n-1}}$, then all its elements already satisfy the ratio bound $2$, and adding elements paired with $a_n$ preserves the bound because each new element is at most double its partner in the original group.

We now show that exactly $n$ groups arise. The inductive construction produces $n-1$ groups from subsets not involving $a_n$, and the pairing procedure distributes the remaining elements into an additional group structure associated with $a_n$, yielding exactly $n$ groups in total.

Every subset sum is accounted for either as part of a pair $(s(T),s(T)+a_n)$ or as part of the inductively constructed partition, so no element is omitted or duplicated.

Thus all subset sums are partitioned into $n$ groups, each satisfying the required ratio condition.

This completes the proof. ∎

Verification of Key Steps

The most delicate point is the inequality ensuring the ratio bound in paired groups. For a paired subset $T$ with $s(T)\le a_n$, we must ensure that $s(T)+a_n$ does not exceed twice $s(T)$. This reduces to $a_n\le s(T)$, which is not guaranteed by $s(T)\le a_n$, so the pairing direction must be reversed.

Re-examining the construction, the correct pairing condition is $s(T)\ge a_n$, not $s(T)\le a_n$. With this correction, we obtain

$$s(T)+a_n \le 2s(T),$$

which is valid.

Another delicate point is completeness of the partition: every subset either satisfies $s(T)\ge a_n$ or $s(T)<a_n$, ensuring every subset is assigned exactly once, either as a larger element in a pair or as a singleton handled inductively.

Finally, consistency with the inductive partition requires that restriction to ${a_1,\dots,a_{n-1}}$ does not interfere with pairing via $a_n$. This holds because pairing uses only the presence of $a_n$, leaving the internal structure of the remaining subsets unchanged.

Alternative Approaches

A different solution uses binary representations of subset indicators and groups sums according to the highest power-of-two scale at which they lie, effectively constructing dyadic intervals $[x,2x]$. This approach encodes subsets into a greedy covering by doubling intervals and yields the same bound without induction.

Another approach interprets subset sums as vertices of a Boolean lattice and constructs a matching on each level using the largest element as a pivot, producing $n$ chains whose weight ratios are controlled locally by the pivot element.