The problem is to find in which value of n the {1,2,3,...n} set can be parted in 3 subsets such that each one has equal sum. I have looked for a lot for this answer, but I can't solve it to the end. The minimum such number is 5. {5},{1,4},{2,3} I know that if this sum 1+2+3+...+n is divisible by 3 and n>=5 , then it is possible. If 1+...+n is equal to 3*a, then if I show that there exist 2 subsets such that each one has its elements sum equal to a , then problem will be solved, I can show the that there exist one, but not the second. Please help if you can.
Asked
Active
Viewed 159 times
-1
-
Your third sentence says that if $T(n) = 1 + ... + n$ is divisible by $3$ and $n \ge 5$, then you know it is possible. And you know $n = 5$ works. So you've answered the question ("find which values of $n$"). Or are you uncertain how to check whether $T(n)$ is divisible by $3$? – John Hughes Feb 21 '16 at 12:40
-
Because $T(n) = n*(n+1)/2$, and for numbers of the form $n = 3k$ and $n = 3k - 1$, these are always divisible by $3$, but for $n = 3k-2$, they are not. So that completes your list. – John Hughes Feb 21 '16 at 12:42
1 Answers
0
This comes down to showing: If this works for $n$ then it also works for $n+3$. This we can do inductively.
So, suppose that you can do the division for $\{1,\dots, n\}$. Say the subsets are $S_1,S_2,S_3$ and let's further suppose that $1\in S_1$. We note that $$T(n+3)=T(n)+(n+1)+(n+2)+(n+3)=T(n)+3n+6\implies \frac {T(n+3)}3=\frac {T(n)}3+n+2$$
thus our goal is to add $n+2$ to each of the subsets $S_1,S_2,S_3$. Again, the new integers we have to do work with are $\{n+1,n+2,n+3\}$.
to do this: Add $n+2$ to $S_3$. Put $n+3$ into $S_1$ and move the $1$ into $S_2$. Adding the $n+1$ to $S_2$ then completes the task.
lulu
- 70,402