# Dividing first n integers into subsets

I was wondering when first $n$ integers can be divided into 2 subsets with equal sum. It is obviously possible in case of even numbers Eg $n =4$ $$\{1,2,3,4 \} \Rightarrow \{1,4\}, \{2,3\}$$ It is not possible for $n$ of the form $4k+1$ as sum to $n$ integers is odd. But it is possible for $n$ of the form $4k-1$ (I think) Eg $n =7$ $$\{1,2,3,4,5,6,7\} \Rightarrow \{1,3,4,6\}, \{2,5,7\}$$ Can someone prove this?

• Welcome to MSE. Please use MathJax. – José Carlos Santos Dec 5 '17 at 16:29
• “It is obviously possible in case of even numbers” — No. The simplest counterexample, $n=2$, already appears in the answer, but actually it is false for any even number of the form $n=4k+2$, as the sum of all numbers then is $(4k+2)(4k+3)/2 = (2k+1)(4k+3)$ and thus odd. – celtschk Dec 6 '17 at 8:08

The natural approach is to use induction. It's false for $n=1$ or $n=2$, but it works for $n=3$. So the proposition as stated so broadly is just plain false.
So let's consider your narrower claim that it's true for $n = 3~(mod~4)$. It's certainly true for $n=3$. Assume it's true for $k = 3~(mod~ 4)$. Thus you have partitioned all these integers $\{1, ..., k\}$into two subsets $A$ and $B$ the sums of whose elements are equal. Then when you add four more integers in sequence, you can take the first and fourth new integers and append them to $A$, and you can take the second and third new integers and append them to $B$. Then their sums are still equal.
• When $n = 3$, it works for $A=\{1,2\}$ and $B=\{3\}$. The sums of the elements of these sets is not even. – Eric Fisher Dec 6 '17 at 8:29
• I meant the sum of all numbers. $1+2+3=6$ which is quite obviously even. It is quite obvious that if that sum is not even, there's no way to divide the set into two subsets with equal sum; the not so obvious part is that the sum being even is already a sufficient condition. – celtschk Dec 6 '17 at 16:10