
4. Find for which natural numbers $n$ it is possible to decompose the set $M=$ $\{1,2, \ldots, n\}$ into a) two b) three mutually disjoint subsets having the same number of elements and such that each of them also contains the arithmetic mean of all its elements.


Solution. a) Denote the desired subsets by $A$ and $B$. Since they both have the same number of elements, the number of elements of $M$ must be even. Thus $n=2 k$, where $k$ is a natural number.

For $n=4$ no such decomposition of $M=\{1,2,3,4\}$ into two subsets can exist, since the arithmetic mean of two distinct numbers cannot be equal to either of these numbers. Let us construct a desired decomposition of the set $M$ for the first few even values of the number $n$ (the arithmetic mean of the elements in the subsets is set in boldface).

$$
\begin{array}{lll}
n=2: & A=\{\mathbf{1}\} & B=\{\mathbf{2}\} \\
n=4: & & \text { decomposition does not exist } \\
n=6: & A=\{1, \mathbf{2}, 3\} & B=\{4, \mathbf{5}, 6\} \\
n=8: & A=\{2,3, \mathbf{4}, 7\} & B=\{1, \mathbf{5}, 6,8\} \\
n=10: & A=\{1,2, \mathbf{3}, 4,5\} & B=\{6,7, \mathbf{8}, 9,10\} \\
n=12: & A=\{1,2,3, \mathbf{4}, 6,8\} & B=\{5,7, \mathbf{9}, 10,11,12\}
\end{array}
$$

We now show that the desired decomposition of $M$ exists for any $n=2 k$, where $k \neq 2$.

If $k$ is odd, then one possible decomposition is given by

$$
A=\{1,2, \ldots, k\}, \quad B=\{k+1, k+2, \ldots, 2 k\} .
$$

The sum of all the elements of $A$ is $\frac{1}{2} k(k+1)$, their arithmetic mean equals $\frac{1}{2}(k+1)$, which is a natural number. Since $1 \leqslant \frac{1}{2}(k+1) \leqslant k$, the arithmetic mean of all the elements of $A$ is an element of $A$. Similarly, the arithmetic mean $\frac{1}{2}(3 k+1)$ of all elements of the subset $B$ is an element of $B$.

For $k=4$ the existence of the decomposition is shown in the above table; for even numbers $k \geqslant 6$ a possible decomposition is given by

$$
A=\left\{1,2, \ldots, k-2, k, \frac{1}{2}(3 k-2)\right\}, \quad B=M \backslash A
$$

We have $k<\frac{1}{2}(3 k-2) \leqslant 2 k$ and $\frac{1}{2}(3 k-2)$ is a natural number. The set $A$ thus contains $k$ natural numbers from the set $M$. The sum of all the elements of $A$ is

$1+2+\cdots+(k-2)+k+\frac{1}{2}(3 k-2)=\frac{1}{2}(k-2)(k-1)+k+\frac{1}{2}(3 k-2)=\frac{1}{2} k(k+2)$.

Their arithmetic mean is $\frac{1}{2}(k+2)$, which is a natural number. Since $1 \leqslant \frac{1}{2}(k+2) \leqslant$ $k-2$, the arithmetic mean of all the elements of $A$ is an element of $A$. Similarly one shows that the arithmetic mean $\frac{3}{2} k$ of all elements of $B$ is an element of $B$.

b) Let $A, B$ and $C$ denote the desired subsets of the set $M$. Since they all have the same number of elements, $n$ must be divisible by 3 , hence of the form $n=3 k$, where $k$ is a natural number. The sum $s$ of all elements of $M$ equals $s=\frac{1}{2} 3 k(3 k+1)$. The sum of the three arithmetic means of the elements in the subsets $A, B$ and $C$,
respectively, is thus equal to $s / k$, that is, $\frac{3}{2}(3 k+1)$. By the hypotheses, this sum must be a natural number, thus $k$ must be odd.

On the other hand, for numbers of the form $n=3 k$, where $k$ is odd, a possible decomposition is given by

$$
A=\{1,2, \ldots, k\}, \quad B=\{k+1, k+2, \ldots, 2 k\} \quad \text { and } \quad C=\{2 k+1,2 k+2, \ldots, 3 k\}
$$

Indeed, the sum of all elements in $A$ is $\frac{1}{2} k(k+1)$, hence their arithmetic mean is $\frac{1}{2}(k+1)$, which is a natural number; and since $1 \leqslant \frac{1}{2}(k+1) \leqslant k$, this arithmetic mean is an element of $A$. Similarly we show that the arithmetic mean $\frac{1}{2}(3 k+1)$ of all the elements of $B$ is an element of $B$, and the arithmetic mean $\frac{1}{2}(5 k+1)$ of all the elements of $C$ is an element of $C$.

Conclusion. In part a), the possible numbers $n$ are all even $n$ different from 4 ; in part b), all odd $n$ divisible by three.
