(EGMO 2017) Find the smallest positive integer $k$ for which there exists a $k$-coloring of the positive integers and a function $f: \mathbb{N}^{*} \rightarrow \mathbb{N}^{*}$ such that

1. $\forall n, m \in \mathbb{N}^{*}$ of the same color, $f(n+m)=f(n)+f(m)$
2. $\exists n, m \in \mathbb{N}^{*}$ such that $f(n+m) \neq f(n)+f(m)$
Obviously, at least two colors are needed to satisfy point (2). Moreover, we notice that 3 colors suffice: we color in blue the integers congruent to 0 modulo 3, in red those congruent to 1, and in yellow those congruent to 2 modulo 3, and the function

$$
f: n \in \mathbb{N}^{*} \mapsto \begin{cases}n & \text { if } n \equiv 0[3] \\ 2 n & \text { otherwise }\end{cases}
$$

It remains to show that two colors are not enough. For this, we assume that there exists a two-color coloring (black and white) and a suitable function $f$. Let $n$ be the smallest integer such that $f(n) \neq n f(1)$. $n$ is odd, otherwise $f(n)=2 f\left(\frac{n}{2}\right)$; we assume that $n$ is black. For all $i \in \llbracket 1, \frac{n-1}{2} \rrbracket, i$ and $n-i$ are of different colors. If there exists an odd integer $j \in \llbracket 1, n-1 \rrbracket$ that is black, $f(n+j)=f(n)+f(j) \neq(n+j) f(1)$ and $f(n+j)=2 f\left[\frac{n+j}{2}\right]=(n+j) f(1)$, which is impossible. Since there are only two colors, all even integers are black and all odd integers are white. We then have two possibilities for the color of $n+1$, knowing that $f(n+1)=f(2+(n-1))=2 f(1)+(n-1) f(1)=(n+1) f(1)$:

- If $n+1$ is white like $n-1, f(2 n)=f((n+1)+(n-1))=f(n+1)+f(n-1)=$ $(n+1) f(1)+(n-1) f(1)=2 n f(1)$. But we also have $f(2 n)=2 f(n) \neq 2 n f(1)$.
- If $n+1$ is black like $1, f(n+2)=f(n+1)+f(1)=(n+2) f(1)$. But we also have $f(n+2)=f(n)+f(2) \neq(n+2) f(1)$.

Thus, we cannot color $n+1$ either white or black, which is absurd.

The minimum number of colors possible for a satisfying coloring is therefore indeed 3.