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:
Choose an element $x_i$ from $X$ that satisfies $|S_{i-1} + x_i| <1000$ and remove it from $X$.
$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)