Kvant Math Problem 688
Let
Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m16s
Source on kvant.digital
Problem
Given natural numbers $a_1$, $a_2$, $\ldots$, $a_n$ such that $a_k \le k$ $(k=1,2, \ldots,n)$ and the sum $a_1+a_2+\ldots+a_n$ is even. Prove that one of the expressions $$a_1\pm a_2\pm a_3\pm \ldots \pm a_n$$ is equal to zero.
S. Nenashev
Exploration
Let
$$S=a_1+a_2+\cdots+a_n.$$
Since $a_k\le k$, we have
$$S\le 1+2+\cdots+n=\frac{n(n+1)}2.$$
The condition that $S$ is even suggests rewriting the problem as a partition problem. Choosing signs $\pm$ is equivalent to splitting the numbers into two groups with equal sum. Indeed,
$$a_1\pm a_2\pm\cdots\pm a_n=0$$
means that the sum of the terms carrying the plus sign equals the sum of the terms carrying the minus sign, both being $S/2$.
Thus the problem becomes: prove that some subset of ${a_1,\dots,a_n}$ has sum $S/2$.
Try small cases.
For $n=1$, necessarily $a_1=1$, whose sum is odd, so this case never occurs.
For $n=2$, the only possibility with even total sum is $(1,1)$, and
$$1-1=0.$$
For $n=3$, possible sequences are
$$(1,1,2),\ (1,2,1),\ (1,2,3).$$
Their sums are $4,4,6$, and each has a subset summing to half the total.
The bound $a_k\le k$ resembles the classical fact that with numbers
$$1,2,\dots,n$$
one can form every integer from $0$ to $1+2+\cdots+n$ as a subset sum. More generally, if a sequence satisfies
$$a_1\le 1,\qquad a_k\le 1+\sum_{i<k}a_i,$$
then all sums from $0$ to $S$ occur as subset sums. Here we have the stronger condition $a_k\le k$.
Let
$$T_{k-1}=a_1+\cdots+a_{k-1}.$$
Because $a_i\ge1$ for all $i$,
$$T_{k-1}\ge k-1.$$
Hence
$$a_k\le k\le T_{k-1}+1.$$
This is exactly the hypothesis of the subset-sum interval lemma. If all integers from $0$ to S occur as subset sums, then in particular $S/2$ occurs, since $S$ is even. That immediately yields the desired choice of signs.
The delicate point is proving rigorously that the subset sums form the whole interval $[0,S]$.
Problem Understanding
We are given positive integers
$$a_1,\dots,a_n$$
such that
$$a_k\le k \qquad (k=1,\dots,n),$$
and the total sum
$$S=a_1+\cdots+a_n$$
is even.
We must prove that signs can be assigned so that
$$a_1\pm a_2\pm\cdots\pm a_n=0.$$
This is a Type B problem. The claim is already stated and must be proved.
The core difficulty is showing that some subset of the numbers has sum exactly $S/2$. The condition $a_k\le k$ must be converted into a structural statement about attainable subset sums.
Proof Architecture
Lemma 1. For every $k\ge2$,
$$a_k\le 1+\sum_{i=1}^{k-1}a_i.$$
This follows because each $a_i\ge1$, hence the partial sum of the first $k-1$ terms is at least $k-1$.
Lemma 2. If positive integers $b_1,\dots,b_m$ satisfy
$$b_1\le1,\qquad b_j\le1+\sum_{i<j}b_i\quad(j\ge2),$$
then every integer from $0$ to $b_1+\cdots+b_m$ is representable as a subset sum of the $b_i$.
This is proved by induction on $m$.
Lemma 3. Every integer from $0$ to
$$S=a_1+\cdots+a_n$$
is a subset sum of the numbers $a_1,\dots,a_n$.
Apply Lemmas 1 and 2.
Main step. Since $S$ is even, the integer $S/2$ is a subset sum. The corresponding subset and its complement have equal sums, yielding a sign assignment whose value is $0$.
The lemma most likely to fail under scrutiny is Lemma 2, because the interval structure of subset sums must be established without gaps.
Solution
Let
$$S=a_1+a_2+\cdots+a_n.$$
Since the numbers are natural,
$$a_i\ge1$$
for all $i$.
For each $k\ge2$,
$$a_1+\cdots+a_{k-1}\ge k-1,$$
because the sum contains $k-1$ positive integers. Hence
$$a_k\le k\le\bigl(a_1+\cdots+a_{k-1}\bigr)+1.$$
Also,
$$a_1\le1.$$
We now prove a general lemma.
Let positive integers
$$b_1,\dots,b_m$$
satisfy
$$b_1\le1, \qquad b_j\le1+\sum_{i=1}^{j-1}b_i \quad (j\ge2).$$
Write
$$B=b_1+\cdots+b_m.$$
We claim that every integer between $0$ and $B$ is a subset sum of the numbers $b_1,\dots,b_m$.
The proof is by induction on $m$.
For $m=1$, the condition $b_1\le1$ and positivity imply $b_1=1$. The subset sums are $0$ and $1$, which are exactly all integers in $[0,1]$.
Assume the claim holds for $m-1$. Put
$$T=b_1+\cdots+b_{m-1}.$$
By the inductive hypothesis, every integer in the interval $[0,T]$ is a subset sum of
$$b_1,\dots,b_{m-1}.$$
The subset sums not using $b_m$ therefore fill the interval
$$[0,T].$$
The subset sums using $b_m$ fill the interval
$$[b_m,b_m+T].$$
Since
$$b_m\le T+1,$$
the intervals $[0,T]$ and $[b_m,b_m+T]$ overlap or are adjacent. Their union is therefore the entire interval
$$[0,b_m+T]=[0,B].$$
Thus every integer from $0$ to $B$ is a subset sum, completing the induction.
Applying this lemma to the sequence
$$a_1,\dots,a_n,$$
we obtain that every integer from $0$ to $S$ is a subset sum of these numbers.
Because $S$ is even, the integer
$$\frac S2$$
lies in the interval $[0,S]$. Hence there exists a subset
$$I\subseteq{1,\dots,n}$$
such that
$$\sum_{i\in I}a_i=\frac S2.$$
Let
$$J={1,\dots,n}\setminus I.$$
Then
$$\sum_{j\in J}a_j = S-\frac S2 = \frac S2.$$
Assign the sign $+$ to the terms with indices in $I$ and the sign $-$ to the terms with indices in $J$. Then
$$\sum_{i\in I}a_i-\sum_{j\in J}a_j = \frac S2-\frac S2 = 0.$$
Thus one of the expressions
$$a_1\pm a_2\pm\cdots\pm a_n$$
is equal to zero.
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the deduction
$$a_k\le1+\sum_{i<k}a_i.$$
The hypothesis gives only $a_k\le k$. Since each preceding term is a positive integer,
$$\sum_{i<k}a_i\ge k-1.$$
Therefore
$$1+\sum_{i<k}a_i\ge k,$$
and combining this with $a_k\le k$ yields the desired inequality. If positivity were omitted, this argument would fail.
The second delicate step is the induction lemma. After obtaining the intervals
$$[0,T] \quad\text{and}\quad [b_m,b_m+T],$$
one must justify that no gap exists between them. The inequality
$$b_m\le T+1$$
is exactly equivalent to
$$b_m-1\le T.$$
Hence the second interval starts no later than one unit after the first ends, so every integer from $0$ to $b_m+T$ belongs to one of the two intervals.
The final step is the conversion from a subset of sum $S/2$ to a sign assignment. If
$$\sum_{i\in I}a_i=\frac S2,$$
then the complementary subset automatically has the same sum because the total is $S$. Writing one subset with plus signs and the other with minus signs produces value $0$ exactly.
Alternative Approaches
One can formulate the proof in terms of reachable differences rather than subset sums. Process the numbers in order. After the first $k-1$ terms, suppose every integer in some symmetric interval $[-T,T]$ can be realized as a signed sum. Since
$$a_k\le T+1,$$
adding the term $a_k$ with either sign expands the attainable differences to the whole interval
$$[-(T+a_k),,T+a_k].$$
An induction then shows that every integer between $-S$ and $S$ is attainable, in particular $0$.
The subset-sum formulation is preferable because the condition that the total sum is even immediately identifies the target value $S/2$, and the interval lemma for subset sums is both shorter and more transparent.