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.)
 re: No problems | Comment 5 of 7 |
(In reply to No problems by Steve Herman)

Hi,  Steve

You have shown that for n>5 and sum(n) divisible by 3 there is

always at least one way to reach the "3E-Partition".

You just  gave two examples how it is done and, believe me, that is exactly the way I would tackle the problem
for, say, n=65.

However the presence of solution is not mathematically, i.e. strictly proven.

To leave no stone unturned,  I  suggest showing that once
a solution exist for  (1,2,3,... n),  creating a  3E-Partition  for (1,2,3,...n+2, n+3) is trivial .

My proof:

Let the 3E-Partition  for sum(n)  be S1, S2, S3.

We have to add 3 additional numbers n+1 , n+2 ,n+3 i.e. to increase each subset by n+2.

We will replace number 1 (present in one of the subsets, say S2) by n+3;  the number n+2 will go to another subset (e.g. S1) without replacement.

Two unassigned numbers 1 and n+1 go to the last subset
(S3  in our example).

Since existence of a solution for n=5 and 4=6 was shown
de facto, the process of full induction is concluded.

Your remarks and rating of the post will be appreciated.

Btw, you  previously wrote:

" We can rule out 3 and 4, so the only numbers that might work are 6,8,9,11,12,14,15, etc."

To justify the word "only", please edit and add the number 5 as capo de lista.

 Posted by Ady TZIDON on 2010-05-27 06:19:31

 Search: Search body:
Forums (0)