, 2010

Prove the claim by induction on $n$. If $n=2$, then the only way to choose integers that satisfy the conditions of the problem is $a_1 = 1$ and $a_2 = 1$. In this case, $a_1 - a_2 = 0$.

Assume now that the claim holds whenever $2 \le n \le k$ and show that it holds also for $n = k + 1$. Consider two cases.

1. If $a_{k+1} = a_k$, then $a_1 + a_2 + \dots + a_{k-1}$ is even. As this case is possible only for $k > 2$, the induction hypothesis is applicable for $n = k - 1$. Thus it is possible to choose signs in the expression $a_1 \pm a_2 \pm \dots \pm a_{k-1}$ in such a way that it evaluates to $0$. Adding $a_k - a_{k+1}$ to it, the desired expression for $n = k + 1$ is obtained.

2. If $a_k \neq a_{k+1}$, then consider integers $a_1, \dots, a_{k-1}, |a_k - a_{k+1}|$. As $|a_k - a_{k+1}|$ and $a_k + a_{k+1}$ have the same parity, the sum of these $k$ numbers is even. Also note that $1 \le |a_k - a_{k+1}| \le k$. Thus these numbers satisfy the conditions of the problem, so it is possible to choose signs in the expression $a_1 \pm a_2 \pm \dots \pm a_{k-1} \pm |a_k - a_{k+1}|$ in such a way that it evaluates to $0$. As either $|a_k - a_{k+1}| = a_k - a_{k+1}$ or $|a_k - a_{k+1}| = a_{k+1} - a_k$, this also leads to a corresponding expression for numbers $a_1, a_2, \dots, a_k, a_{k+1}$.

Prove by induction on $i$ that, for each $i$ and $s$ such that $1 \le i \le n$ and $1 \le s \le a_1 + \dots + a_i$, it is possible to choose some of the numbers $a_1, \dots, a_i$ that sum up to $s$.

If $i = 1$, then this claim holds since $a_1 = 1$.

Assume that the claim holds for $i = k - 1$ and consider the case $i = k$. Let $S = a_1 + \dots + a_k$ and $S' = a_1 + \dots + a_{k-1}$. If $1 \le s \le S'$, then the desired statement holds by the induction hypothesis. If $S' < s \le S$, then $0 \le s - a_k \le S'$ (the first inequality holds because $s - a_k \ge s - S' - 1 \ge 0$, implied by $a_k \le k$ and $S' \ge k - 1$; the second inequality follows from $S = S' + a_k$). Therefore, to get the sum $s$, we can choose the number $a_k$, and if $s - a_k > 0$, then add to it those numbers among $a_1, \dots, a_{k-1}$ whose sum is $s - a_k$, using the induction hypothesis.

Let now $a_1 + a_2 + \dots + a_n = 2T$. Choose the numbers among $a_1, a_2, \dots, a_n$ that sum up to $T$. This divides all the numbers into two groups with equal sum. It remains to write minuses in front of every term of the group that does not contain $a_1$.

Start choosing signs from right to left. Denote $S_1 = a_n$ and define $S_{k+1}$, $k = 1, \dots, n-1$, as follows: if $S_k \ge 0$, then $S_{k+1} = S_k - a_{n-k}$, otherwise $S_{k+1} = S_k + a_{n-k}$.

We show that then always $|S_k| \le n-k+1$. This holds if $k=1$. Assume therefore that it holds for $k=m$ and prove it for $k=m+1$. If $S_m \ge 0$, then $S_{m+1} = S_m - a_{n-m} \le (n-m+1)-1 = n-m$ and $S_{m+1} = S_m - a_{n-m} \ge 0 - (n-m)$, hence $|S_{m+1}| \le n-m$. If $S_m < 0$, then $S_{m+1} = S_m + a_{n-m} < 0 + n-m$ and $S_{m+1} = S_m + a_{n-m} \ge -(n-m+1)+1 = -(n-m)$, hence $|S_{m+1}| \le n-m$ again.

Now $|S_n| \le 1$ since $|S_k| \le n-k+1$ for every $k=1, \dots, n$. Thus $S_n = 0$ as the sum of all terms is even. If in this formal sum, the term $a_1$ has minus sign, turn all signs to the opposite one.