# Combinatorics Proof Suggestions and Feedback

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!