# Partition onto subsets at the same sum

Positive integers $a_1, a_2,\ldots, a_n$ such that $a_k\leq k$ and the sum of all these numbers is even and equal to $2S$. Prove that the number can be divided into two groups, the amount of each of which is equal to $S$.

It's look like I have to use induction, but I can not figure out how...Please give me a hint.

• It might be a pigeonhole type argument that wins the day. Note that the assumption $a_k \le k$ is essential as we cannot partition $\{1,2,3,8\}$ into two subsets, each of which has sum equal to seven. – hardmath May 6 '15 at 20:09

It seems to me you can use induction and the following transformation on sequences $(a_1,\ldots,a_n)$ of positive integers with $a_i\le i$ and even sum: $$(a_1,\ldots,a_{n-1},a_n)\mapsto \begin{cases} (a_1,\ldots,a_{n-2})&\text{if}\quad a_{n-1}=a_n,\\ (a_1,\ldots,a_{n-2},|a_n-a_{n-1}|)&\text{if}\quad a_{n-1}\not=a_n. \end{cases}$$ The resulting sequence is of the same kind and also has even sum. This may be continued until the sequence vanishes, which means an expression on the form $\pm a_1\pm\cdots\pm a_n=0$ was formed.