Kvant Math Problem 1222

Let the given integers be considered modulo $m$.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m46s
Source on kvant.digital

Problem

Let $m\gt1$ be a positive integer, and let $s$ be the greatest integer for which $2^s\le m$. Prove that

  1. for any $s+1$ integers, one can choose several of them and place plus and minus signs between them so that the resulting sum is divisible by $m$;
  2. the estimate in part (a) is best possible: there exist $s$ integers such that no sum of several of them, under any placement of signs, is divisible by $m$.

V. F. Lev

Exploration

Let the given integers be considered modulo $m$. Choosing several of them and inserting signs $\pm$ is equivalent to choosing coefficients from ${-1,0,1}$, not all zero. Thus part (a) asks for a nontrivial relation

$$\varepsilon_1a_1+\cdots+\varepsilon_{s+1}a_{s+1}\equiv0\pmod m, \qquad \varepsilon_i\in{-1,0,1}.$$

The number $s$ is defined by

$$2^s\le m<2^{s+1}.$$

A counting argument suggests itself. For $k$ numbers there are $2^k$ subset sums. If $k=s+1$, then $2^{s+1}>m$, so among the $2^{s+1}$ subset sums two must be congruent modulo $m$. Their difference is a signed sum with coefficients in ${-1,0,1}$, and the difference of two distinct subsets cannot give all coefficients equal to $0$. This proves part (a).

For part (b), one needs $s$ integers for which no nontrivial signed sum is divisible by $m$. Powers of two are natural because signed binary expansions are unique in a suitable range. Take

$$1,2,4,\dots,2^{s-1}.$$

Any signed sum

$$\sum_{i=0}^{s-1}\varepsilon_i2^i, \qquad \varepsilon_i\in{-1,0,1},$$

has absolute value at most

$$1+2+\cdots+2^{s-1}=2^s-1<m.$$

Hence divisibility by $m$ would force the sum to be $0$. The crucial point is to show that the only signed combination of these powers of two equal to $0$ is the trivial one. Looking at the largest index with nonzero coefficient gives uniqueness: if $r$ is maximal with $\varepsilon_r\ne0$, then

$$\left|\sum_{i<r}\varepsilon_i2^i\right| \le 2^r-1,$$

so it cannot cancel $\varepsilon_r2^r$.

That yields the extremal example.

Problem Understanding

We are given a positive integer $m>1$ and the integer $s$ determined by

$$2^s\le m<2^{s+1}.$$

Part (a) asks us to prove that among any $s+1$ integers one can select some of them and assign signs $+$ and $-$ so that the resulting signed sum is divisible by $m$.

Part (b) asks us to show that $s+1$ is the smallest number with this property. In other words, there exist $s$ integers for which no nonempty signed sum is divisible by $m$.

This is a Type B problem. The core difficulty is establishing the sharpness statement. The counting argument for part (a) is straightforward, but part (b) requires an explicit family of $s$ integers and a proof that no nontrivial signed combination of them can vanish modulo $m$.

Proof Architecture

First lemma: among the $2^{s+1}$ subset sums of $s+1$ integers, two have the same residue modulo $m$; this follows from the pigeonhole principle because $2^{s+1}>m$.

Second lemma: the difference of two distinct subsets produces a nontrivial signed sum with coefficients in ${-1,0,1}$ that is divisible by $m$; this converts equal subset sums into the required conclusion.

Third lemma: for the numbers $1,2,\dots,2^{s-1}$ written as powers of two, every nontrivial signed sum has absolute value at least $1$ and at most $2^s-1$; the upper bound comes from the geometric series formula.

Fourth lemma: the powers of two are linearly independent over the coefficient set ${-1,0,1}$, namely

$$\sum_{i=0}^{s-1}\varepsilon_i2^i=0$$

implies all $\varepsilon_i=0$; choose the largest index with nonzero coefficient and compare magnitudes.

The hardest direction is part (b). The lemma most likely to fail under insufficient scrutiny is the uniqueness of the signed binary representation.

Solution

Let the given integers be $a_1,\dots,a_{s+1}$, considered modulo $m$.

For every subset $I\subseteq{1,\dots,s+1}$, define

$$S(I)=\sum_{i\in I}a_i .$$

There are exactly $2^{s+1}$ such subset sums. Since

$$2^{s+1}>m,$$

while there are only $m$ residue classes modulo $m$, the pigeonhole principle yields two distinct subsets $I$ and $J$ such that

$$S(I)\equiv S(J)\pmod m.$$

Hence

$$\sum_{i\in I}a_i-\sum_{i\in J}a_i\equiv0\pmod m.$$

For each index $i$, let

$$\varepsilon_i= \begin{cases} 1,& i\in I\setminus J,\ -1,& i\in J\setminus I,\ 0,& i\in I\cap J\ \text{or}\ i\notin I\cup J. \end{cases}$$

Then

$$\varepsilon_1a_1+\cdots+\varepsilon_{s+1}a_{s+1}\equiv0\pmod m.$$

Since $I\ne J$, at least one coefficient $\varepsilon_i$ is nonzero. Thus we have obtained a sum of several of the given integers with signs $+$ and $-$ whose value is divisible by $m$. This proves part (a).

For part (b), consider the $s$ integers

$$1,2,4,\dots,2^{s-1}.$$

Suppose that a signed sum of several of them is divisible by $m$. Then

$$T=\sum_{i=0}^{s-1}\varepsilon_i2^i, \qquad \varepsilon_i\in{-1,0,1},$$

satisfies

$$T\equiv0\pmod m.$$

Since

$$|T| \le \sum_{i=0}^{s-1}2^i =2^s-1 <m,$$

the only multiple of $m$ whose absolute value is smaller than $m$ is $0$. Hence

$$T=0.$$

It remains to prove that this forces all coefficients $\varepsilon_i$ to vanish.

Assume the contrary. Let $r$ be the largest index for which $\varepsilon_r\ne0$. Then

$$\left|\sum_{i=0}^{r-1}\varepsilon_i2^i\right| \le \sum_{i=0}^{r-1}2^i =2^r-1.$$

On the other hand,

$$|\varepsilon_r2^r|=2^r.$$

Therefore

$$\left|\varepsilon_r2^r+\sum_{i=0}^{r-1}\varepsilon_i2^i\right| \ge 2^r-(2^r-1) =1.$$

Consequently,

$$\sum_{i=0}^{r}\varepsilon_i2^i\ne0,$$

contradicting $T=0$.

Thus every $\varepsilon_i$ equals $0$. No nonempty signed sum of

$$1,2,4,\dots,2^{s-1}$$

is divisible by $m$.

Parts (a) and (b) together show that $s+1$ is the best possible bound.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the conversion of equal subset sums into a signed sum. If

$$S(I)\equiv S(J)\pmod m,$$

then moving all terms from the second side to the first gives coefficients $1$, $-1$, or $0$ according to membership in $I\setminus J$, $J\setminus I$, or neither. Because $I\ne J$, at least one coefficient is nonzero. Without checking this last point, one could accidentally obtain the trivial relation.

The second delicate step is the claim that divisibility by $m$ forces the signed sum of powers of two to be zero. The estimate

$$|T|\le2^s-1$$

is strict because $2^s\le m$. Hence

$$|T|<m.$$

A nonzero multiple of $m$ has absolute value at least $m$, so only $T=0$ is possible.

The third delicate step is proving that

$$\sum_{i=0}^{s-1}\varepsilon_i2^i=0$$

has only the trivial solution. Let $r$ be the largest index with $\varepsilon_r\ne0$. The lower powers contribute at most

$$2^r-1,$$

which is strictly smaller than the magnitude $2^r$ of the leading term. Thus cancellation is impossible. Any argument that merely appeals to “uniqueness of binary expansion” would be incomplete because the coefficients may also be negative.

Alternative Approaches

Part (a) may also be phrased in terms of residues of subset sums. Arrange all $2^{s+1}$ subset sums modulo $m$. Either one of them is already congruent to $0$, or two distinct subset sums coincide modulo $m$. The first case immediately yields the desired signed sum with only plus signs, while the second case is handled by subtraction. This is essentially the same counting argument in a different presentation.

For part (b), another proof uses congruences modulo powers of two. Suppose

$$\sum_{i=0}^{s-1}\varepsilon_i2^i=0.$$

Reducing modulo $2$ gives $\varepsilon_0=0$. Dividing by $2$ and reducing modulo $2$ again gives $\varepsilon_1=0$. Repeating this process successively yields $\varepsilon_2=\cdots=\varepsilon_{s-1}=0$. The maximal-index argument used in the main proof is shorter and avoids an iterative descent.