Divide the set {1,2,3,4, ....,n} into three disjoint subsets A , B , C whose sums of elements are equal.
For what values of n it is feasible?
This is possible for all positive integers of the form 3a and 3a+2 except for 2 and 3.
First it can never work for numbers of the form 3a+1 since the sum of the numbers would be (3a+1)(3a+2)/2 which is never divisible by 3.
This is feasible for n = 5,6,8,and 9
n=5: {1,4}{2,3}{5}
n=6: {1,6}{2,5}{3,4}
n=8: {1,3,8}{2,4,6}{5,7}
n=9: {1,5,9}{2,6,7}{3,4,8}
If n is feasible then n+6 is feasible.
The extra numbers are n+1, n+2, n+3, n+4, n+5, n+6
partition them into {n+1, n+6}, {n+2, n+5}, {n+3, n+4}
and add the elements of one of these partitions to each of A, B, C.

Posted by Jer
on 20100527 11:32:44 