5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – hardmath May 6 '15 at 20:09
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.