# Find all $n$ such that $1,2,\dots,n$ be divided into disjoint triples such that for each triple, one element is the sum of the other two elements.

Find all $$n$$ such that $$\{1,2,\dots,n\}$$ be divided into disjoint triples such that for each triple, one element is the sum of the other two elements.

On a 2013 combinatorics handout (high school Math Olympics) of tian27546西西 (translated into English)

Assume $$\{1,2,\dots,n\}$$ be divided into disjoint triples, then $$3\mid n$$. And because each triple can be written in the form of $$(a,b,a+b)$$, the sum of the elements of each triple is even, so $$1+2+\dots+n=n(n+1)/2$$ is even, so $$n$$ must be in the form of $$12k$$, or $$12k+3$$.

Lemma: Assume that there is a division for $$n=k$$, then there is a division for $$n=4k$$ or $$n=4k+3$$.

Proof: $$\{2,4,⋯,2k\}$$ can be divided in the same way as $$\{1,2,⋯,n\}$$. For $$n=4k$$, the remaining numbers $$\{1,3,⋯,2k-1,2k+1,2k+2,⋯,4k-1,4k\}$$ can be divided into $$k$$ triples $$(2j-1,3k-j+1,3k+j),j=1,2,⋯,k$$, as follows (each column is a triple): $$\begin{pmatrix}1 & 3 & 5 & \cdots & 2 k-3 & 2 k-1 \cr 3 k & 3 k-1 & 3 k-2 & \cdots & 2 k+2 & 2 k+1 \cr 3 k+1 & 3 k+2 & 3 k+3 & \cdots & 4 k-1 & 4 k\end{pmatrix}$$ For $$n=4k+3$$, the remaining numbers $$\{1,3,⋯,2k-1,2k+1,⋯,4k+2,4k+3\}$$ can be divided into $$k+1$$ triples $$(2i-1,3k+3-j,3k+j+2),j=1,2,⋯,k+1$$, we also get the following (each column is a triple) :$$\begin{pmatrix}1 & 3 & 5 & \cdots & 2 k-1 & 2 k+1 \cr 3 k+2 & 3 k+1 & 3 k & \cdots & 2 k+3 & 2 k+2 \cr 3 k+3 & 3 k+4 & 3 k+5 & \cdots & 4 k+2 & 4 k+3\end{pmatrix}$$ Example: Since for $$n=3$$ there is a division, and$$3 \longrightarrow_{3 \times 4+3} 15 \longrightarrow_{15 \times 4} 60 \longrightarrow_{60 \times 4+3} 243 \longrightarrow_{243 \times 4+3} 975$$so there is a division for $$n=975$$.

All $$n$$ that can be reduced to $$3$$, are $$3, 12, 15, 48, 51, 60, 63,\dots$$(See A001196)

There are $$n$$ that satisfies the condition but can not be reduced to $$3$$, the smallest ones are $$24,27,36,39$$. Using the lemma, each of them can produce other numbers. $$\begin{array}l n=24& \begin{pmatrix} 1 & 3 & 5 & 8 & 4 & 7 & 6 & 2 \\ 23 & 19 & 16 & 12 & 14 & 10 & 9 & 11 \\ 24 & 22 & 21 & 20 & 18 & 17 & 15 & 13 \end{pmatrix}\\ n=27& \begin{pmatrix} 5 & 3 & 6 & 9 & 8 & 7 & 4 & 2 & 1 \\ 11 & 14 & 12 & 10 & 13 & 15 & 20 & 23 & 26 \\ 16 & 17 & 18 & 19 & 21 & 22 & 24 & 25 & 27 \end{pmatrix}\\ n=36&\begin{pmatrix} 6 & 8 & 4 & 7 & 12 & 11 & 10 & 9 & 5 & 3 & 2 & 1 \\ 15 & 14 & 19 & 17 & 13 & 16 & 18 & 20 & 26 & 30 & 32 & 35 \\ 21 & 22 & 23 & 24 & 25 & 27 & 28 & 29 & 31 & 33 & 34 & 36 \end{pmatrix}\\ n=39&\begin{pmatrix} 7 & 5 & 8 & 6 & 13 & 12 & 11 & 10 & 9 & 4 & 3 & 2 & 1 \\ 15 & 19 & 17 & 20 & 14 & 16 & 18 & 21 & 23 & 30 & 33 & 35 & 38 \\ 22 & 24 & 25 & 26 & 27 & 28 & 29 & 31 & 32 & 34 & 36 & 37 & 39 \end{pmatrix} \end{array}$$ Originally posted by user realnumber on Math Entertainment forum. I found the above divisions for $$24,27,36,39$$ by Mathematica.

• Commented Sep 14, 2022 at 21:19

A108235 Number of partitions of $$\{1,2,...,3n\}$$ into $$n$$ triples $$(X,Y,Z)$$ each satisfying $$X+Y=Z$$. $$\{a_1,a_2,\dots\}=\{1, 0, 0, 8, 21, 0, 0, 3040, 20505, 0, 0, 10567748, 103372655,\\ 0, 0, 142664107305, 1836652173363, 0, 0,\dots\}$$ The desired sequence is$$\{3n:a_n\ne0\}=\{3, 12, 15, 24, 27, 36, 39, 48, 51,\dots\}$$