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?
I am assuming that the union of A,B,C must be {1,2,3,...,n}
a method for even n immediately comes to mind
let n be even
then we can break the set down into n/2 groups of two as such
{1,n}
{2,n-1}
{3,n-2}
....
{n/2,(n+2)/2}
all of which have the equal sum of n+1
so now all we need is for there to be at least three of these, thus n/2>=3 or n>=6
and we can simply construct A,B, and C from these groupings by placing each of them into one of the three sets.
For even numbers n<6 we have n=2 and n=4
if n=2 then we obviously don't have enough elements for three disjoint subsets
if n=4 then it is equally impossible to form such a set.
Thus it is possible to form A,B, and C for all even n>=6
what remains is to determine criteria for odd n
|
|
Posted by Daniel
on 2010-05-26 16:52:29 |
half of it
