All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Make it equal (Posted on 2010-05-26)
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?

Comments: ( Back to comment list | You must be logged in to post comments.)
 No problems | Comment 4 of 7 |
Well, apparently it can be done for any positive integer n, where n*(n+1) is divisible by three, except for 2 and 3.  In other words, 3k or 3k-1, where k > 2.

In other words: 5, 6, 8,9, 11,12, etc.
Each partition sums to n*(n+1)/6

5 has only one partition: {5}, {4,1}, {3,2}
6 has {6,1}, {5,2},{4,3}

But everything higher has more than one available partition.
One partition which is always available:  Start with the highest available number and keep adding into its partition the highest unused number which will not cause it to exceed n*(n+1)/6. When that partition is equal to n*(n+1)/6, start with the highest unused number and add that to the second partition.  Keep adding in the highest unused numbers which will will not cause it to exceed n*(n+1)/6. When it equals n*(n+1)/6, all remaining numbers go in the 3rd partition.  (And yes, I haven't proved this will always work, but there are so many small integers available that I am confident it can't fail).

For instance, n = 8.  Partition total = 8*9/6 = 12
Method above gives: {8,4}, {7,5}, {6,3,2,1}

For instance, n = 9.  Partition total = 9*10/6 = 15
Method above gives: {9,6}, {8,7}, {5,4,3,2,1}

For instance, n = 11.  Partition total = 11*12/6 = 22
Method above gives: {11,10,1}, {9,8,5}, {7,6,4,3,2}

 Posted by Steve Herman on 2010-05-27 01:32:23

 Search: Search body:
Forums (0)