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 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.