
5. Find for which

$$
n \in\{3900,3901,3902,3903,3904,3905,3906,3907,3908,3909\}
$$

the set $\{1,2,3, \ldots, n\}$ can be partitioned into (disjoint) triples in such a way that one of the three numbers in any triple is the sum of the other two.


Solution. From the possibility of partitioning the set into disjoint triples it follows that $3 \mid n$. In each triple $\{a, b, a+b\}$ the sum of its elements is $2(a+b)$, hence an even number; thus also the sum of all numbers from 1 to $n$ must be even, i.e. the product $n(n+1)$ must be divisible by four. Altogether it therefore follows that the number $n$ has to be of the form either $12 k$ or $12 k+3$; from the given set of numbers, this is satisfied only for $n=3900$ and $n=3903$.

In the next paragraph we describe a construction how to produce, starting from a decomposition satisfying the given condition for some $n=k$, a decomposition of the same kind for $n=4 k$ and $n=4 k+3$. This guarantees that the required decompositions for $n=3900$ and $n=3903$ indeed exist, in view of the decreasing sequence

$$
3900 \rightarrow 975 \rightarrow 243 \rightarrow 60 \rightarrow 15 \rightarrow 3
$$

(instead of 3900 one can start also with 3903 ) and the trivial decomposition for $n=3$ (from which we in turn construct the decompositions for $n=15, n=60$ etc. up to $n=3900$ or $n=3903$ ).

From a decomposition of the set $\{1,2, \ldots, k\}$ satisfying the given conditions we first produce a similar decomposition for the set of the first $k$ even numbers $\{2,4, \ldots, 2 k\}$ (simply by multiplying all the numbers in the triples by two). In the case of $n=4 k$ we partition the remaining numbers

$$
\{1,3,5, \ldots, 2 k-1,2 k+1,2 k+2, \ldots, 4 k-1,4 k\}
$$

into the $k$ triples $\{2 j-1,3 k-j+1,3 k+j\}$, where $j=1,2, \ldots, k$. They are shown in the columns of the table below.

$$
\left(\begin{array}{cccccc}
1 & 3 & 5 & \ldots & 2 k-3 & 2 k-1 \\
3 k & 3 k-1 & 3 k-2 & \ldots & 2 k+2 & 2 k+1 \\
3 k+1 & 3 k+2 & 3 k+3 & \ldots & 4 k-1 & 4 k
\end{array}\right)
$$

In the case of $n=4 k+3$ we partition the remaining numbers

$$
\{1,3,5, \ldots, 2 k-1,2 k+1,2 k+2, \ldots, 4 k+2,4 k+3\}
$$

into the $k+1$ triples $\{2 j-1,3 k+3-j, 3 k+j+2\}$, where $j=1,2, \ldots, k+1$; these are again shown in the columns of the table below.

$$
\left(\begin{array}{cccccc}
1 & 3 & 5 & \ldots & 2 k-1 & 2 k+1 \\
3 k+2 & 3 k+1 & 3 k & \ldots & 2 k+3 & 2 k+2 \\
3 k+3 & 3 k+4 & 3 k+5 & \ldots & 4 k+2 & 4 k+3
\end{array}\right)
$$

This completes the proof of the fact that the solution of the given problem are the numbers $n=3900$ and $n=3903$.
