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

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

• I wrote a script using Knuth's dancing links to check this. For all $n\le 48$ for which $n\equiv 0\text{ or }5\pmod 8$, my script found a solution in a couple of seconds, except for $n=45$. After 10 minutes, I gave up. This doesn't prove there is no solution for 45, but it suggests it. (Here are the solutions I found: pastebin.com/MyYaPd6t). Commented Jun 23, 2021 at 18:28
• I wrote a blog post that might be of interest: Richard Guy studied the analog where $x + y = 2z$. blog.peterkagey.com/2021/05/richard-guys-partition-sequence Commented Jun 23, 2021 at 19:21
• I found one for $45$ with simmulated annealing. Commented Jun 23, 2021 at 20:05
• what a nice question aqua! Might be easier to think of the condition as $\frac{\text{sum}(A_i)}{4} \in A_i$. Commented Jun 24, 2021 at 23:02

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?

• does this solve the problem, with the computer evidence we already have? Commented Jun 30, 2021 at 4:33
• No, but it means there are arbitrarily large solutions. Commented Jun 30, 2021 at 4:50
• Can you please post you update answer as new question with linked here. Perhaps someone will have new idea with this generalzation of yours. Commented Jul 4, 2021 at 15:29
• Aren’t the numbers $15N+12,…21N+14$ used up twice, one for each of the two types of subsets? Commented Jul 4, 2021 at 18:08
• The +2k means that One type has odd numbers,, the other has even ones. Commented Jul 4, 2021 at 19:17

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

• Thanks! Can you check about partitioning $\{1,2,\dots,5n\}$ into $n$ subsets each of size $5$ so that in each subset $\{v,w,x,y,z\}$ we have $v+w+x+y = 5z$? Of course, only certain $n$ work. Commented Jun 29, 2021 at 23:43
• @mathworker21 Your $5n$ variant requires that $12 \mid 5n(5n+1)$, so $n \equiv 0,3,4,7 \pmod{12}$. There are solutions for all eight such values of $n$ up through $n=24$. Commented Jun 30, 2021 at 3:17
• Thank you very much. That's very helpful to know. Commented Jun 30, 2021 at 3:18