Problem. We are given $2000$ integers each with absolute value less than $1000$ and with the sum equal to $1$. Prove that we can choose some of them with sum equal to $0$.

Here is my solution:

Suppose the numbers are $X = \{a_1, a_2, ..., a_{2000} \}$.

First choose a random $a_i$ and call it $x_1$. Let $S_1 = x_1$ and we construct $(S_i)_{1 \leq i \leq n}$ with the following recursive algorithm:

  1. Choose an element $x_i$ from $X$ that satisfies $|S_{i-1} + x_i| <1000$ and remove it from $X$.

  2. $S_i = S_{i-1} + x_i$, in particular, $|S_i| < 1000$.

I claim that it is always possible to find such an $x_i$ to satisfy step $1$. Assume the contrary, that is, there exists $S_k = x_1 + x_2 + ... + x_k$ and no $x_{k+1}$ exists.

WLOG, we can assume $S_k > 0$. So, for every $a_i \in X$, we have that $a_i \geq 1000 - S_k$. But this is impossible since $a_1 + a_2 + ... + a_{2000} = 1$.

Thus we can generate

\begin{align*} S_1 & = x_1 \\ S_2 & = x_1 + x_2 \\ & \vdots \\ S_{2000} & = x_1 + x_2 + ... + x_{2000} \end{align*} We know that $-999 \leq S_1, S_2, ..., S_{2000} \leq 999$ so by Pigeon-hole, at least two $S_i$ are equal. But we can subtract these two to get a subset of $a_i$ that sum to $0$.

Does anyone have any feedback to make this clearer? Also I would love to see another solution!


This problem comes from Canadian Olympiads 2000.

It can be found (together with a solution, based, as yours, on the pigeon hole principle), as Problem #3 in (https://cms.math.ca/Concours/OMC/archive/sol2000.pdf)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.