The question is : Let n be greater than or equal to $2$, and let $a_1, a_2, \cdots, a_n$ be positive integers whose sum is even, and such that $a_i \le i$. Prove that it is possible to choose signs for each number as such: $\pm a_1 \pm a_2 \pm \cdots \pm a_n$ In such a way such that the sum is zero.
So I'm really stuck on this. I know that the sum has to be even due to the fact that you can split up the positives and the negatives. But I'm really stuck after that. Any help or solutions?
One can accomplish this by choosing the signs $s_n,s_{n-1},\dots,s_2,s_1\in\{-1,1\}$ of $a_n,a_{n-1},\dots,a_2,a_1$, in that order, as follows:
Choose $s_n$ arbitrarily. For each $k\in\{n-1,n-2,\dots,2,1\}$, choose $s_k$ to be the negative of the sign of $s_{k+1}a_{k+1} + \cdots + s_na_n$. (If that sum equals $0$, choose $s_k$ arbitrarily.)
It's simple to show inductively that with this scheme (and under the assumption $1\le a_k\le k$), we have $|s_ka_k + \cdots + s_na_n| \le k$ for each $k\in\{n,n-1,\dots,2,1\}$. In particular, $|s_1a_1 + \cdots + s_na_n| \le 1$.
The above didn't even use the fact that the $a_j$ are integers (only the bounds $1\le a_k\le k$). But if the $a_j$ are integers, then $s_1a_1 + \cdots + s_na_n$ is also an integer that has the same parity as $a_1 + \cdots + a_n$. In particular, if that latter sum is even, then $s_1a_1 + \cdots + s_na_n$ is an even integer that is at most $1$ in absolute value, hence must equal $0$.