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$?

Question

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

Answer 1

Here is the integer linear programming approach I used to find partitions for all such $n\le 496$ with $n \equiv 0,5 \pmod 8$. First enumerate all triples $\{x,y,z\}$ with $x+y=3z$ and $x,y,z$ distinct elements of $[3n]:=\{1,\dots,3n\}$. For each such triple $T$, let binary decision variable $u_T$ indicate whether $T$ appears in the partition. The constraints $$\sum_{T:\ i\in T} u_T = 1 \quad \text{for $i\in[3n]$} \tag1$$ enforce that each element appears exactly once in the partition.

An alternative approach is to introduce nonnegative slack variables $s_i$, replace the set partitioning constraints $(1)$ with (set covering and cardinality) constraints \begin{align} \sum_{T:\ i\in T} u_T + s_i &\ge 1 &&\text{for $i\in[3n]$} \tag2 \\ \sum_T u_T &= n \tag3 \end{align} and minimize $\sum_{i=1}^{3n} s_i$. A partition of $[3n]$ into $n$ triples with $x+y=3z$ exists if and only if the optimal objective value is $0$.

Answer 2

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?