MHB Find All Integers for Equal Sum Disjoint Union Sets

[lfdahl]

Find all integers $n$ such that the set $\{1,2,3,4, ...,n\}$ can be written as the disjoint union of the subsets $A$ , $B$ , $C$ whose sum of elements are equal.

 

[topsquark]

Find all integers $n$ such that the set $\{1,2,3,4, ...,n\}$ can be written as the disjoint union of the subsets $A$ , $B$ , $C$ whose sum of elements are equal.

Wouldn't that just be all (non-negative) integers such that n is divisible by 3??

-Dan

 

[kaliprasad]

Find all integers $n$ such that the set $\{1,2,3,4, ...,n\}$ can be written as the disjoint union of the subsets $A$ , $B$ , $C$ whose sum of elements are equal.

Spoiler

sum of n integers has to be multiple of 3.

So the number of numbers has to be 3n + 3 or 3n + 2

each set can not contain 1 element each then the sum cannot be equal

so start with 5 we have 3 set $5,(1,4),(2,3)$

for 6 we have $(1,6),(2,5),(3,4)$

for 9 (from magic square we get $(2,9,4), (3,5,7), (8,1,6)$

for 8 we have $(8,4), (2,7,3), (1,5,6)$

now for any number of the form $3n + 2 ( n >=4)$ is of the form $9k + 2 ( 9(k-1) + 6 + 5)$ or $9k + 5$ or $9k + 8$

by grouping as above we can get any number of the from 3n + 2 into 3 equal part and of the form 3n into equal parts

so number of the from $3n + 2$ or $3n + 3$ (n >= 1) (same as 3k with k >=2)

 

[topsquark]

...sum of elements...

Got it now.

-Dan

 

[lfdahl]

Thankyou, kaliprasad, for your participation

I believe, the suggested solution below is in overall agreement with your considerations:

Spoiler

Since \[\sum_{x\in A}x +\sum_{x\in B}x+ \sum_{x\in C}x = \frac{n(n+1)}{2}\]

the RHS must be divisible by $3$ and therefore $n$ is congruent to one of $0,2,3,5$ modulo $6$.
Now we prove, that if $n$ is congruent to one of $0,2,3,5$ modulo $6$ and $n > 4$, then such a partition exists.

If we can find such partition for some $n$, then we can enlarge it to an admissible partition for $n+6$ by adjoining $n+1$ and $n+6$ to $A$; $n+2$ and $n+5$ to $B$; $n+3$ and $n+4$ to $C$.
For $n = 5,6,8,9$ we have the following partitions:

$n = 5 \;\;\;\;\;\;A = \{1,4\}\;\;\;\;\;\;B=\{2,3\}\;\;\;\;\;\;C = \{5\}$

$n = 6\;\;\;\;\;\;A = \{1,6\}\;\;\;\;\;\;B=\{2,5\}\;\;\;\;\;\;C = \{3,4\}$

$n = 8\;\;\;\;\;\;A = \{1,2,3,6\}\;\;\;\;B=\{5,7\}\;\;\;\;\;C = \{4,8\}$

$n = 9\;\;\;\;\;\;A = \{1,2,3,4,5\}\;\;\;B=\{7,8\}\;\;\;\;\;C = \{6,9\}$

Obviously, for $n \le 4$ such a partition does not exist.