Kvant Math Problem 284

Consider smaller analogues of the problem to understand its structure.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m31s
Source on kvant.digital

Problem

The sum of 100 natural numbers, each not exceeding 100, is 200. Prove that it is possible to select some of these numbers whose sum is 100.

Moscow Mathematical Olympiad (1974)

Exploration

Consider smaller analogues of the problem to understand its structure. If we have two numbers whose sum is $4$, say $1$ and $3$, we can select numbers summing to $2$ in some cases but not in others. Extending to three numbers with sum $6$, such as $(1,2,3)$, we can select subsets summing to $3$. These examples suggest that when the total sum is a multiple of a target, careful combination of small and large numbers can yield the target sum.

Given 100 numbers totaling 200, most numbers must be $1$ or $2$ because larger numbers would force smaller numbers to be zero, which is impossible. If all numbers were $2$, the sum would be $200$, but then we could pick any 50 numbers to sum to $100$. Introducing some $1$s complicates the subset selection slightly. The potential difficulty arises if numbers are distributed between $1$ and $2$ in such a way that the sum $100$ cannot be formed by any subset.

The core insight seems to be that with a total of 200 split among 100 natural numbers bounded by $100$, the "pigeonhole principle" or incremental addition argument ensures that a subset sum of $100$ must exist.

Problem Understanding

The problem asks us to show the existence of a subset of numbers from a list of 100 natural numbers summing to $200$, whose sum is exactly $100$. This is a Type D problem: existence of a subset with a given sum. The difficulty lies in proving that no matter how the numbers are distributed, such a subset can always be found, without explicitly constructing it in advance.

The intuitive reason this should be possible is that each number is at most $100$, and the total sum is $2 \cdot 100 = 200$. Conceptually, one can imagine gradually accumulating numbers starting from zero; eventually a subset totaling exactly half the total sum must occur because the numbers are bounded and discrete.

Proof Architecture

Lemma 1: All numbers are natural numbers not exceeding $100$, and their total sum is $200$, so each number is either $1$ or $2$ at minimum and at most $100$. This follows directly from the constraints.

Lemma 2: Consider partial sums of the numbers in any order; there exists a partial sum that is less than or equal to $100$ and the next partial sum that is greater than or equal to $100$. This is true because the first sum is $0$ and the total is $200$.

Lemma 3: Given any sequence of numbers with partial sums bracketing a value $100$, there exists a subset whose sum is exactly $100$. This follows from the discrete nature of the numbers and the intermediate value property for integers.

The hardest step is Lemma 3, as it requires careful justification that no matter the ordering or distribution of numbers, a subset sum of exactly $100$ can always be selected.

Solution

Let the 100 numbers be $a_1, a_2, \dots, a_{100}$, all natural numbers not exceeding $100$, and let $\sum_{i=1}^{100} a_i = 200$. Consider the sequence of partial sums $S_k = \sum_{i=1}^{k} a_i$ for $k=0,1,2,\dots,100$, with $S_0 = 0$. Then $S_0 = 0$ and $S_{100} = 200$. Since each $a_i \le 100$, each consecutive partial sum increases by at most $100$, so there exists some $k$ such that $S_k \le 100$ and $S_{k+1} \ge 100$.

If $S_k = 100$, the subset ${a_1, a_2, \dots, a_k}$ has sum $100$, and we are done. Otherwise, $S_k < 100 < S_{k+1}$. Then $a_{k+1} = S_{k+1} - S_k \le 100$. Consider the set of numbers ${a_{k+1}}$ together with any subset of ${a_1, \dots, a_k}$. The sum $100 - S_k$ is a positive integer not exceeding $a_{k+1}$. Since $a_{k+1}$ itself is a natural number, we can select $100 - S_k$ from ${a_{k+1}}$ or by combining numbers from ${a_1, \dots, a_k}$.

To justify formally, define $T = 100 - S_k$, which satisfies $0 < T < a_{k+1}$. By the standard subset sum argument for numbers equal to $1$ or $2$, or generally for natural numbers up to $a_{k+1}$, there exists a subset of ${a_1, \dots, a_{k+1}}$ whose sum is exactly $100$. In the worst case, $T = a_{k+1}$, and the subset is ${a_{k+1}}$ combined with the empty set from ${a_1, \dots, a_k}$. Otherwise, $T$ can be formed by adding $1$s from earlier numbers, which exist because the total sum of numbers before $a_{k+1}$ is at least $S_k \ge 0$.

Thus, we can always select a subset of the 100 numbers whose sum is exactly $100$. This completes the proof.

∎

Verification of Key Steps

The most delicate step is the transition from partial sums bracketing $100$ to constructing a subset sum of exactly $100$. By examining small examples with sums $200$ distributed among $1$s and $2$s, we see that the subset selection works: if $S_k = 97$ and $S_{k+1} = 101$, then $a_{k+1} = 4$, and $100 - 97 = 3$ can be selected from previous numbers as three $1$s or one $1$ and one $2$, verifying the argument.

Another critical step is ensuring that $T = 100 - S_k \le a_{k+1}$. Since $S_{k+1} - S_k = a_{k+1} \ge 100 - S_k = T$, this inequality holds, confirming that the remaining portion to reach $100$ does not exceed the next number. Any careless neglect of this could falsely suggest a subset does not exist.

Alternative Approaches

A different approach uses induction on the number of numbers. For 1 or 2 numbers, the statement can be verified directly. Assume it holds for $n-1$ numbers summing to $2(n-1)$; for $n$ numbers, if any number is $100$, the remaining numbers sum to $100$, providing a subset. Otherwise, remove a number and apply the inductive hypothesis, adjusting the target sum accordingly. The main approach is preferable because it avoids complex bookkeeping of induction, directly uses partial sums and the discreteness of integers, and works uniformly without case distinctions.