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 2010-05-27 11:32:44