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?

(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