Partitioning of sets

Question

Question:

Consider set $A= \{ 1, 2, 3, ..., n\}$. For what values of $n$ can $A$ be partitioned into 3 subsets $A_1, A_2, A_3$, such that sum of the elements of each of them are equal?

My Attempt:

For the set $A$ to be partitioned in the required way, sum of all elements of $A$ must be divisible by $3$. Thus a necessary condition is:

$1 + 2 + .. + n = n(n+1)/2 \equiv 0 $ mod $3$

which implies $n = 3t $ or $n = 3t-1$ for integer $t>2$

On trial with values of t up to $t=11$, I found that in every case, $A$ can be partitioned according to the given conditions. But how can I prove this?

Answer 1

Partial answer: For $n=3t$ define the sets: $$A_1 = \{1+6k:1\leq 1+6k\leq n\}\cup \{6k:1\leq 6k \leq n\}=\{1,6,7,12,13,\ldots \}$$ $$A_2 = \{2+6k:1\leq 2+6k\leq n\}\cup \{5+6k:1\leq 5+6k \leq n\}=\{2,5,8,11,14,\ldots \}$$ $$A_3 = \{3+6k:1\leq 3+6k\leq n\}\cup \{4+6k:1\leq 4+6k \leq n\}=\{3,4,9,10,15,\ldots \}$$

Edit: Adding complete solution. For $n=3t-1$ take: $$A_1 = \{5+6k:1\leq 5+6k\leq n\}\cup \{6k:1\leq 6k \leq n\}=\{5,6,11,12,17,\ldots \}$$ $$A_2 = \{1+6k:1\leq 1+6k\leq n\}\cup \{4+6k:1\leq 4+6k \leq n\}=\{1,4,7,10,13,\ldots \}$$ $$A_3 = \{2+6k:1\leq 2+6k\leq n\}\cup \{3+6k:1\leq 3+6k \leq n\}=\{2,3,8,9,14,\ldots \}$$

Answer 2

You could use induction with an enforced inductionhypothese.

Let it be that there are partitions $\{A_1^{(n)},A_2^{(n)},A_3^{(n)}\}$ and $\{B_1^{(n)},B_2^{(n)},B_3^{(n)}\}$ of set $\{1,\dots,n\}$ such that $$\sum_{k\in A_1^{(n)}}k=\sum_{k\in A_2^{(n)}}k=\sum_{k\in A_3^{(n)}}k$$ and $$\sum_{k\in B_1^{(n)}}k<\sum_{k\in B_2^{(n)}}k<\sum_{k\in B_3^{(n)}}k$$ where these numbers are consecutive.

Now we claim that we can make such partitions also for set $\{1,\dots,n,n+1,n+2,n+3\}$.

We can take $B^{(n+3)}_i=A_i^{(n)}\cup\{n+i\}$ and $A^{(n+3)}_i=B_i^{(n)}\cup\{n+4-i\}$ for $i=1,2,3$.

---

To make things complete: you can start e.g. with:

$A_{1}^{\left(8\right)}=\left\{ 4,8\right\} $, $A_{2}^{\left(8\right)}=\left\{ 2,3,7\right\} $ and $A_{3}^{\left(8\right)}=\left\{ 1,5,6\right\} $

$B_{1}^{\left(8\right)}=\left\{ 3,8\right\} $, $B_{2}^{\left(8\right)}=\left\{ 1,4,7\right\} $ and $B_{3}^{\left(8\right)}=\left\{ 2,5,6\right\} $

$A_{1}^{\left(9\right)}=\left\{ 1,5,9\right\} $, $A_{2}^{\left(9\right)}=\left\{ 7,8\right\} $ and $A_{3}^{\left(9\right)}=\left\{ 2,3,4,6\right\} $

$B_{1}^{\left(9\right)}=\left\{ 1,6,7\right\} $, $B_{2}^{\left(9\right)}=\left\{ 2,5,8\right\} $ and $B_{3}^{\left(9\right)}=\left\{ 3,4,9\right\} $

Answer 3

Sum of arithmetical seqence: $x, x+3, x+6, \ldots, x+3(a-1)$ is $\frac { x + (x+3(a-1))}{2}a $.

Hence for theree sequences sequences beginning from $x=1,2,3$ and of lenghts: $a,b,c$ accordlingly, we have the sum of these three sequnces:

$\frac{3a-1}{2}a + \frac{3b+1}{2}b + \frac{3c+3}{2}c = 3\frac{a^2+b^2+c^2}{2}-a+b+3c$.

In the case when $3|n$ we can choose: $a=n/3, b=n/3, c=n3$.

In the case when $3|(n-1)$ we can choose: $a=(n-1)/3, b=(n-1)/3, c=(n+2)/3$.

In both cases total sum is $\frac{n^2+n}{2}$ as we hope.