4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Welcome to MSE. Please use MathJax. $\endgroup$ – José Carlos Santos Dec 5 '17 at 16:29
  • $\begingroup$ “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. $\endgroup$ – celtschk Dec 6 '17 at 8:08
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So it is possible exactly if the sum of the numbers is even. $\endgroup$ – celtschk Dec 6 '17 at 8:12
  • $\begingroup$ When $n = 3$, it works for $A=\{1,2\}$ and $B=\{3\}$. The sums of the elements of these sets is not even. $\endgroup$ – Eric Fisher Dec 6 '17 at 8:29
  • 1
    $\begingroup$ 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. $\endgroup$ – celtschk Dec 6 '17 at 16:10
  • $\begingroup$ The sum of the first n integers is n(n+1)/2. You’re right. The proposition is also true for k = 0 (mod 4). The same proof works, with the initial case of n=4. When So it’s necessary and sufficient that the sum be even. $\endgroup$ – Eric Fisher Dec 8 '17 at 8:25

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.