9. determine the largest natural number $k$ with the following property: The set of natural numbers can be divided into $k$ disjoint subsets $A_{1}, \ldots, A_{k}$ in such a way that every natural number $n \geq 15$ can be written as the sum of two different elements from $A_{i}$ for every $i \in\{1, \ldots, k\}$.
Solution For $k=3$ you can divide the natural numbers as follows:

$$
\begin{aligned}
& A_{1}=\{1,2,3\} \cup\{3 m \mid m \geq 4\} \\
& A_{2}=\{4,5,6\} \cup\{3 m-1 \mid m \geq 4\} \\
& A_{3}=\{7,8,9\} \cup\{3 m-2 \mid m \geq 4\}
\end{aligned}
$$

In $A_{1}$ all numbers $n \geq 12+1=13$ can be represented as a sum, in $A_{2}$ all $n \geq 11+4=15$ and in $A_{3}$ all $n \geq 10+7=17$. The numbers 15,16 are also sums of two elements from $A_{3}$ because $7+8=15$ and $7+9=16$.

Now assume $k \geq 4$. If $A_{1}, \ldots, A_{k}$ fulfill the condition, then surely $A_{1}, A_{2}, A_{3}, \bigcup_{4 \leq i \leq k} A_{i}$, so we can assume $k=4$. Set $B_{i}=A_{i} \cap\{1,2, \ldots, 23\}$. Then each of the numbers 15, 16, . . 23 must be written as a sum of two different elements from $B_{i}$, i.e. $\left|B_{i}\right| \geq 5$. On the other hand, $\left|B_{1}\right|+\left|B_{2}\right|+\left|B_{3}\right|+\left|B_{4}\right|=23$, so there is an $i$ with $\left|B_{i}\right|=5$, write $B_{i}=\left\{x_{1}, x_{2}, \ldots, x_{5}\right\}$. Now note that the 10 numbers $15,16, \ldots 24$ can all be written as the sum of two different elements from $B_{i}$, but with different elements from $B_{i}$ you can form at most 10 such sums. We therefore sum over all such sums and obtain

$$
4\left(x_{1}, \ldots, x_{5}\right)=15+16+\cdots+24=195
$$

is a contradiction, since 195 is not divisible by 4.