[Math] For which $n\in\Bbb N$ can we divide $\{1,2,3,…,3n\}$ into $n$ subsets each with $3$ elements such that in each subset $\{x,y,z\}$ we have $x+y=3z$

combinatorial-designscombinatoricsconstructive-mathematicscontest-mathgraph theory

For which $n\in \mathbb{N}$ can we divide the set $\{1,2,3,\ldots,3n\}$ into $n$ subsets each with $3$ elements such that in each subset $\{x,y,z\}$ we have $x+y=3z$?

Since $x_i+y_i=3z_i$ for each subset $A_i=\{x_i,y_i,z_i\}$, we have $$4\sum _{i=1}^n z_i=\sum _{i=1}^{3n}i = {3n(3n+1)\over 2} \implies 8\mid n(3n+1) $$
so $n=8k$ or $n=8k-3$. Now it is not difficult to see that if $k=1$ we have such partition.

  • For $n=5$ we have:
    $$A_1= \{9,12,15\}, A_2= \{4,6,14\}, A_3= \{2,5,13\}, \\A_4= \{10,7,11\}, A_5= \{1,3,8\}$$
  • For $n=8$ we have:
    $$A_1= \{24,21,15\}, A_2= \{23,19,14\}, A_3= \{22,2,8\}, A_4= \{20,1,7\}, \\A_5= \{17,16,11\}, A_6= \{18,12,10\}, A_7= \{13,5,6\}, A_8= \{9,3,4\}$$

What about for $k\geq 2$? Some clever induction step? Or some ''well'' known configuration?

Source: Serbia 1983, municipal round, 3. grade

Best Answer

If there is a solution for $N$, then there is a solution for $7N+5$.
The solution for $N$ uses up numbers from $1$ to $3N$. Then $$(3N+k, 15N+9+2k, 6N+3+k), k=1..3N+3\\ (12N+8+k,15N+10+2k,9N+6+k), k=1..3N+2$$ sits the numbers from $3N+1$ to $21N+15$ on top of them.

A similar method gives a solution for $25N+8Q$, for all $-13\le Q\le11$, whenever there is a solution for $N\ge 13$. Together with @RobPratt's solution, that covers all $N=8M$ and all $N=8M-3$.

I have started a new question for a different version at Split $\{1,2,...,3n\}$ into triples with $x+y=4z$ and also Split $\{1,...,3n\}$ into triples with $x+y=5z$ - no solutions?

Related Question