Answer: $k=3$. Construction: let \[ f(n) = \begin{cases} n/3 & n\equiv 0 \pmod 3 \\ n & \text{else} \end{cases} \]and color the integers modulo $3$. Now we prove that for $k=2$ such a function $f$ must be linear, even if $f : {\mathbb Z}_{>0} \to {\mathbb R}_{>0}$. Call the colors blue/red and WLOG $f(1) = 1$. First, we obviously have: Claim: $f(2n) = 2f(n)$ for every $n$. Now we proceed by induction in the following way. Assume that $f(1) = 1$, $f(2) = 2$, \dots, $f(2n) = 2n$. For brevity let $m = 2n+1$ be red and assume for contradiction that $f(m) \neq m$. The proof now proceeds in four steps. First: The number $m-2$ must be blue. Indeed if $m-2$ was red we would have $f(2m-2) = f(m) + f(m-2)$ which is a contradiction as $f(2m-2) = 2f(m-1) = 2m-2$ and $f(m-2)=m-2$. The number $2$ must be red. Indeed if it was blue then $f(m) = f(2) + f(m-2) = m$. Observe then that $f(m+2) = f(m)+2$ since $m$ and $2$ are both red. Now we consider two cases: If $m+2$ is red, then $f(2m+2) = f(m+2) + f(m) = (f(m) + 2) + f(m)$. But $2m+2 \equiv 0 \pmod 4$ implies $f(2m+2) = f(4n+4) = 4f(n+1) = 2m+2$, contradiction. If $m+2$ is blue, then $2f(m) = f(2m) = f(m+2) + f(m-2) = f(m) + 2 + (m-2)$. So then $f(m) = m$ again a contradiction. So $f(m) = m$, which completes the induction.

If $k = 2$, let $f(1) = c$ and assume $f(i) = ic$ for $i = 1, 2, \dots, m$, while $f(i + 1) \neq (i + 1)c$. If $m$ is odd then $f(m + 1) = 2f\left(\frac{m + 1}{2}\right) = (m + 1)c$, thus $m = 2n$ is even. Assume that $a, a+b$ are red and $b$ is blue for some $a, b$ such that $f(a + b) \neq f(a) + f(b)$, then for any red $r$ we have $f(r + a + b) = f(r) + f(a + b)$ and $f(r + a) = f(r) + f(a)$. As $f(a + b) \neq f(a) + f(b)$ this implies that $r + a$ is red, as otherwise $f(r + a + b) = f(r + a) + f(b) = f(r) + f(a) + f(b)$. Now assume wlog that 1 is red, then $2n$ must be blue. If $2n + 1$ is red then we instantly get that $f$ is linear using the previous observation. Thus $2n + 1$ is blue. We now show by induction on $j$ that $j$ is red and $2n - j + 1$ is blue for $j = 1, 2, \dots, n$. This is true for $j = 1$. Now, by our previous result, $4n - j + 1 = (2n - j + 1) + 2n$ is blue. Thus if $j + 1$ is blue we get $$2f(2n + 1) = f(4n + 2) = f(4n - j + 1) + f(j + 1) = f(2n) + f(2n - j + 1) + f(j + 1) = (4n + 2)c$$ Contradicting that $f(2n + 1) \neq (2n + 1)c$. Thus $j + 1$ is red and $2n - j$ must be blue as otherwise $f(2n + 1) = f(2n - j) + f(j + 1) = (2n + 1)c$. This completes the induction. In particular, $n + 1$ must be blue, hence $3n + 1$ is blue, and $2f(2n + 1) = f(4n + 2) = f(3n + 1) + f(n + 1) = f(2n) + 2f(n + 1) = (4n + 2)c$, a contradiction. The construction for $k = 3$ is done by coloring mod 3 and taking $f(n) = n$ if $3 \nmid n$ and $f(n) = 2n$ otherwise. This satisfies the first condition and $6 = f(3) \neq f(2) + f(1) = 3$

Let's suppose that there is a coloring with $2$ colors. Since we must have $a,b \in \Bbb{Z}$ with $f(m+n) \neq f(m)+f(n)$, we'll take the pair $(m,n)$ with the property that $m+n$ is minimum, respectively $m$ is minimum ($m\leq n$). Hence $f(a+b)=f(a)+f(b)$, $\forall a,b \in \Bbb{Z}$ with $a+b \leq m+n$ or $a+b=m+n; a=min(a,m,n,b)$. So, if $m>1$: $f(m+n)=f(m-1)+f(n+1)=f(m-1)+f(1)+f(n)=f(m)+f(n)$, contradiction. So $m=1$ and $\forall a,b \in \Bbb{Z}$ with $a+b<1+n$ we get that $f(a+b)=f(a)+f(b)$. Let $M=\{x \vert f(x)=xf(1)\}$. Clearly,$n+1\notin M, \{1,2,3,\ldots,n\} \in M$ and since $f(2x)=2f(x) \forall x\in \Bbb{Z}$ we obtain that $\{n+2,n+4,\ldots,2n\} \in M$. Hence if $n+1$ and any odd number up to $n$ have the same color, then $f(n+1)+f(x)=f(n+1+x) \Leftrightarrow f(n+1)+xf(1)=(n+1+x)f(1)\Rightarrow n+1 \in M$, contradiction. Hence, if $A$ is the set of the numbers with the color red and $B$ is the set of numbers with the color blue: (WLOG $n+1 \in A$) $\{2,4,6,\ldots,n,n+1\} \in A$, while $\{1,3,5,\ldots,n-1\} \in B$. Furthermore, if $n+2 \in B$ $\Rightarrow f(n+3)=f(n+1)+f(2)=f(1)+f(n+2) \Rightarrow n+1 \in M$, contradiction. So $f(2n+2)=2f(n+1)=f(n)+f(n+2)$, again, a discrepancy with the statement $n+1 \in M$. Overall, $k\geq 3$, but it is not so hard to find an example for $k=3$, as stated in the above solutions.

For $k=3$ we just take $f(n)=2017n$ for $n\equiv 0(mod3)$ and $f(n)=n$ for $n\not\equiv 0(mod3)$ and we color numbers $n\equiv 0(mod 3)$ with red , numbers $n\equiv 1(mod 3)$ with blue and numbers $n\equiv 2(mod 3)$ with green. Now we prove that is not possible for $k=1$ and for $k=2$. For $k=1$ it's clearly immposible since we would have $f(m+n)=f(m)+f(n)$ for all $m,n\in\mathbb{Z}_{>0}$ which condtradict condition $(ii)$ We show that also for $k=2$ is not possible. First since numbers $n$ and $n$ have same color since is the same number then from $(i)$ we have $f(2n)=f(n)+f(n)=2f(n)$. Lets color all numbers with red or blue. We show by induction that $f(n)=nf(1)$. For $n=1$ and $n=2$ it's obvius. Now let suppose that $f(n)=nf(1)$ for all $1\leq n\leq m$ we show that this hold for $n=m+1$ too. Suppose for contrary that $f(m+1)\neq (m+1)f(1)$. If $m$ is odd then since $\frac{m+1}{2}\leq m$ we have $f\left(\frac{m+1}{2}\right)=\left(\frac{m+1}{2}\right)f(1)$ so $f(m+1)=2f\left(\frac{m+1}{2}\right)=2\left(\frac{m+1}{2}\right)f(1)=(m+1)f(1)$ a contradiction. If $m$ is even let be $m=2t$ so $f(2t+1)\neq (2t+1)f(1)$ let suppose that $2t+1$ is blue then $1$ is red otherwise if $1$ is blue, since $t+1\leq 2t$ and from condition $(i)$ we have $f(2t+1)+f(1)=f(2t+1+1)=f(2(t+1))=2f(t+1)=2(t+1)f(1)\Rightarrow f(2t+1)=(2t+1)f(1)$ a contradiction, so $1$ is red. $2t-1$ is red otherwise if $2t-1$ is blue, then from condtion $(i)$ we have $4tf(1)=4f(t)=f(4t)=f(2t-1+2t+1)=f(2t-1)+f(2t+1)=(2t-1)f(1)+f(2t+1)\Rightarrow f(2t+1)=(2t+1)f(1)$ a contradiction, so $2t-1$ is red. $2t$ is blue otherwise if $2t$ is red then from condition $(i)$ we have $f(2t+1)=f(2t)+f(1)=2tf(1)+f(1)=(2t+1)f(1)$ a contradiction, so $2t$ is blue. $2$ is blue otherwise if $2$ is red then from condition $(i)$ we have $f(2t+1)=f(2t-1+2)=f(2t-1)+f(2)=(2t-1)f(1)+2f(1)=(2t+1)f(1)$ a contradiction, so $2$ is blue. If $2t+2$ is blue, since $t+1\leq 2t$ then from condtion $(i)$ we have $2f(2t+1)=f(4t+2)=f(2t+2+2t)=f(2t+2)+f(2t)=2f(t+1)f(1)+2tf(1)=2(t+1)f(1)+2tf(1)=(4t+2)f(1)\Rightarrow$ $f(2t+1)=(2t+1)f(1)$ a contradiction, so $2t+2$ is red, since $t+1\leq 2t$ and from condition $(i)$ we have $f(2t+1)+2f(1)=f(2t+1)+f(2)=f(2t+3)=f(2t+2+1)=f(2t+2)+f(1)=2f(t+1)+f(1)=$ $=2(t+1)f(1)+f(1)=(2t+3)f(1)\Rightarrow f(2t+1)=(2t+1)f(1)$ a contradiction, so $f(2t+1)=(2t+1)f(1)$. So we have $f(n)=nf(1)$ for all $n\in\mathbb{Z}_{>0}$ so $f(m+n)=(m+n)f(1)=mf(1)+nf(1)=f(m)+f(n)$ for all $m,n\in\mathbb{Z}_{>0}$ which contradict condition $(ii)$. So minimal value of $k$ is $k=3$.

The answer is $k=3$, with our construction of coloring by mod 3 and $f(n)=2n$ if $3\mid n$ and $f(n)=n$ otherwise. Clearly it is impossible to have both (i) and (ii) when $k=1$. We will also show that it is impossible for $k=2$ by proving that $f(n)=nf(1)$ for all $n$ by strong induction. As $f(2i)=f(i)+f(i)=2f(i)$ for any $i$, $f(2)=2f(1)$. Now, suppose that $f(m)=mf(1)$ for all $m<n$ for some $n>2$. If $n$ is even, then $f(n)=2f(n/2)=nf(1)$, as desired. Suppose that $n$ is odd and $f(n)\ne nf(1)$. Then, we have that $i$ and $n-i$ are different colors for all $i<n$ as otherwise $f(n)=f(i)+f(n-i)=nf(1)$. We also have that $2i$ and $2(n-i)$ are different colors for any $i<n$ as otherwise $2f(n)=f(2n)=f(2i)+f(2(n-i))=2(f(i)+f(n-i))=2nf(1)$. Hence, $2k-1$ has a different color from $n-2k+1$ has a different color from $n+2k-1$, so $2k-1$ and $n+2k-1$ have the same colors. Thus, $f(n+4k-2)=f(2k-1)+f(n+2k-1)=(2k-1)f(1)+2f((n+2k-1)/2)=(n+4k-2)f(1)$ for all $2k-1<n$, so $f(n+i)=(n+i)f(1)$ for all $i<n$. Thus, $i$ and $2n-i$ are different colors for any $i<n$ as otherwise $f(n)=f(i)+f(2n-i)=nf(1)$. But now note that $n$ can't be the same color as $n-2$ as then we have $f(n)=2f(n-1)-f(n-2)=nf(1)$, and similarly it can't be the same color as $n=2$ as we then have $f(n)=2f(n+1)-f(n+2)=nf(1)$. But this is a contradiction as $n-2$ and $n+2$ are different colors by the above, so we are done.

First of all we show that $k\le 3$: infact if we have $3$ colours we may match them with the three congruence classes $\pmod{3}$ and define $$f\left(n\right)=\begin{cases}n\ \ \text{if}\ \ 3\nmid n\\2n\ \ \text{if}\ \ 3\mid n\end{cases}$$ Now we just have to show that $k>2$. Clearly $k>1$, otherwise $(i)$ and $(ii)$ would contradict eachother. Hence suppose $k=2$ for the sake of contradiction (so the colours will be red and blue). Let's define a function $g:\ \mathbb{Z}^+\rightarrow\mathbb{Q}^+,\ \ g\left(n\right)=\frac{f\left(n\right)}{n}$ For all $d\in2\mathbb{N}+1$ let's define $A_d=\left\{2^xd,\ \ x\in\mathbb{N}\right\}$. By setting $m=n$ in $(i)$ we easily get that the image of $A_d$ through $g$ is a one element set. Now we say that $A_c$ and $A_d$ are friendly if they have the same image through $g$, and unfriendly otherwise. By $(ii)$ we get that there exist unfriendly couples of $A_i$, in particular we take $t$ such that it's the smallest odd positive number such that $A_t$ and $A_1$ are unfriendly. $\text{Case}\ 1$: $A_1$ and $A_t$ aren't one completely red and one completely blue. $\text{Case}\ 1.1$: there exist $j\in\mathbb{N}$ such that $2^jt$ has the same colour of $2^j$ By $(i)$ we get that $$f\left(2^j+2^jt\right)=f\left(2^j\left(t+1\right)\right)=f\left(2^j\right)+f\left(2^jt\right)$$so calling $t_1$ the odd part of $t+1$ ($t_1<t$) we get that $A_{t_1}$ and $A_1$ are unfriendly since $g\left(2^jt_1\right)\ne g\left(2^j\right)$ since $g\left(2^jt_1\right)$ is a weighted average (with positive coefficients) of $g\left(2^j\right)$ and $g\left(2^jt\right)$. But this contradicts how we defined $t$. $\text{Case}\ 1.2$: for all $i\in\mathbb{N}$ we have that $2^i$ and $2^it$ are of different colors (so there exist $j$ such that $2^jt$ and $2^{j+1}$ have the same colour). In this case we will say that $A_1$ and $A_t$ are superunfriendly By $(i)$ we get that $$f\left(2^{j+1}+2^jt\right)=f\left(2^j\left(t+2\right)\right)=f\left(2^{j+1}\right)+f\left(2^jt\right)$$Now, $A_{t+2}$ can't be superunfriendly with both $A_1$ and $A_t$ (since we are supposing that $A_1$ and $A_t$ are superunfriendly). $\text{Case}\ 1.2.1$: $A_{t+2}$ isn't superunfriendly with $A_1$, so there exist $j$ such that $2^j$ and $2^j\left(t+2\right)$ are of the same colour. Hence by $(i)$ we get $$f\left(2^j+2^j\left(t+2\right)\right)=f\left(2^j\left(t+3\right)\right)=f\left(2^j\right)+f\left(2^j\left(t+2\right)\right)$$so calling $t_2$ the odd part of $t+3$ ($t_2\le t$) we can say that $A_{t_2}$ is unfriendly with $A_1$ and with $A_t$ (so $t_2<t$) since $g\left(2^j\left(t+2\right)\right)$ is a weighted average with positive coefficients of $g\left(2^j\right)$ and $g\left(2^j\left(t+2\right)\right)$ wich in turn is a weighted average (with positive coefficients) of $g\left(2^j\right)$ and $g\left(2^jt\right)$. But this contradicts how we defined $t$. $\text{Case}\ 1.2.2$: $A_{t+2}$ isn't superunfriendly with $A_t$, so there exist $j$ such that $2^jt$ and $2^j\left(t+2\right)$ are of the same colour. Hence by $(i)$ we get that $$f\left(2^jt+2^j\left(t+2\right)\right)=f\left(2^j\left(2t+2\right)\right)=f\left(2^jt\right)+f\left(2^j\left(t+2\right)\right)$$so, since $t_1$ is the odd part of $2t+2$ ($t_1<t$) we can say for the same reasons as before that $A_{t_1}$ is unfriendly with $A_1$, but this contradicts how we defined $t$. $\text{Case}\ 2$: $A_1$ and $A_t$ are completely red and completely blue $WLOG$ respectively. $\text{Case}\ 2.1$: there exists an odd number $s<t$ such that $A_s$ contains a blue element $2^us$ (let's keep in mind that $A_s$ is friendly with $A_1$ by how we defined $t$). So by $(i)$ we have$$f\left(2^us+2^ut\right)=f\left(2^u\left(s+t\right)\right)=f\left(2^us\right)+f\left(2^ut\right)$$hence calling $v$ the odd part of $s+t$ ($v<t$) we can say for the same reasons as before that $A_v$ is unfriendly with $A_1$, and this contradicts how we defined $t$. $\text{Case}\ 2.2$: for all odd number $i<t$ we have that $A_i$ is completely red. So let's write $t=1+2^lh$ with $h$ odd ($h$ is as red as $1$ for ipothesis). Hence by $(i)$ we have $$f\left(t\right)=f\left(1+2^lh\right)=f\left(1\right)+f\left(2^lh\right)$$so, since $A_1$ and $A_h$ are friendly by how we defined $t$ we conclude that also $A_t$ should be friendly with $A_1$, contradiction.

We claim that the smallest such $k$ is $3$. First we show that there exist no such coloring and function $f$ for $k=2$. Suppose we were given a 2-coloring on $\mathbb{Z}_{>0}$, and some function $f$ that was additive on a given color. We will show that $f(x)=xf(1)$ for all $x\in\mathbb{Z}_{>0}$. We do this by induction on $x$. Note that $f(2)=f(1)+f(1)=2f(1)$, so suppose that $f(n)=n$ for all $n\in[N]$ where $N\ge 2$. We will now show that $f(N+1)=(N+1)f(1)$. If $N$ is odd, then $f(N+1)=2f((N+1)/2)=2(N+1)/2\cdot f(1)=(N+1)f(1)$, as desired. So we suppose $N=2k$ for some $k\in\mathbb{Z}_{>0}$. If $N+1$ is in the same color group as any odd number $x\in[N]$, then we have $f(N+1)+f(x)=f(N+1+x)=2f((N+1+x)/2)=(N+1+x)f(1)$. Thus, all the odds up till $N$ must be the same color, and if any even number were there, we could find two numbers in that group that added to $N+1$, which would show $f(N+1)=(N+1)f(1)$. Thus, $1,3,\ldots,2k-1$ are all the same color, and $2,4,\ldots,2k,2k+1$ are all the same color. Note that $f(2k+2)=f(2k)+f(2)=(2k+2)f(1)$. If $2k+2$ is in the odd color group, then $f(1)+f(2k+2)=f(2k+3)=f(2k+1)+f(2)$, which easily shows $f(2k+1)=(2k+1)f(1)$. If $2k+2$ is in the even color group, then $f(2k+2)+f(2k)=f(4k+2)=2f(2k+1)$, which also implies the desired result. Thus, in all cases, we have that $f(N+1)=(N+1)f(1)$, completing the induction, so $f(x)=xf(1)$ for all $x$. We now show that there exists a coloring and $f$ for $k=3$ satisfying the desired properties. Let the color groups be the equivalence classes mod $3$, and let $f(x)=x$ if $3\nmid x$, and $f(x)=2x$ if $3\mid x$. It is easy to see that the properties hold, so the answer is $\boxed{k=3}$.

I will give an alternate proof to show that $k=2$ is not possible. So it suffices to show the following: Variant of EGMO 2017 P2 wrote: Partition $\mathbb{N}$ into two non-empty disjoint sets $A, B.$ Show that if $$f(x+y)=f(x)+f(y)$$for all $x,y$ from the same set, then $f(x)=cx$ for all $x \in \mathbb{N},$ where $c \in \mathbb{N}$ is a constant. Firstly note that $f(2^kx)=2^kf(x)$ for all $x \in \mathbb{N}.$ In particular, we will use $f(2x)=2f(x), f(4x)=4f(x).$ Lemma: For all $x,y,z$ of the same set, $f(x+y+z)=f(x)+f(y)+f(z).$

Now, we proceed by strong induction to show that $f(n)=nc,$ where $c=f(1).$ Note that this is true for $n=1,2,3,4.$ (true for $3$ by the lemma) So assume that this is true for $n=1,2, \cdots, k-1.$ We will show that $f(k)=kc.$ If $k=2l$ is even, then we are done since $f(k)=2f(l)=2lc=kc.$ So assume that $k$ is odd; $k=2l+1.$ Also, assume on the contrary that $f(2l+1) \ne (2l+1)c.$ Consider the $l$ pairs $(1,2l), (2, 2l-1), \cdots (l,l+1).$ If any two elements from the same pair appear in the same set, then we trivially have a contradiction. So assume that the two elements of any pair belong to the two opposite sets and wlog $1 \in A.$ If $2 \in B,$ then $2l-1 \in A \implies f(2l+1)=f(2l-1)+f(1)+f(1)=(2l+1)c,$ a contradiction. So $2 \in A.$ If $3 \in B,$ then $2l-2 \in A \implies f(2l+1)=f(2l-2)+f(2)+f(1)=(2l+1)c,$ a contradiction. So $3 \in A.$ We can proceed as above to get that $1,2,3 \cdots, l \in A.$ But then $f(2l+1)=f(l)+f(l)+f(1)=(2l+1)c,$ a contradiction.

For the example of $k=3$ , in fact by setting $f(n)=an$ for $3\mid n$ and $f(n)=bn$ for $3\nmid n$ we get the desired example, where $a,b$ are distinct positive integers. So in fact, all the examples in the above posts have the same root of motivation.

Writing this out just to make sure I didn't make an error in the case bash (writing things out helps). The answer is $k = 3$. The construction in v_Enhance's solution is the one I found too. Now, assume such an $f$ were to exist for $k = 2$. Note that $f(2x) = 2f(x)$ $(*)$ Thus, if $f(1) = c$, then $f(2) = 2c$ Now, let $2n+1$ be the smallest number such that $f(t) \neq ct$. (This number is odd due to $(*)$ for $x = t/2$ for an even $t$.) Such a $t$ must exist as otherwise condition 2 of the problem fails to hold. Let us say $1$ is red (R), and $2n$ is blue(B). Note that $2n - t$ and $t + 1$ must have different colors for $0 \le t \le n - 1$ $(**)$ Now, we case bash!! Case 1 : $2n + 1$ is R. Then, as $(2n + 1) + 1 = 2n + 2$, we have that $2n + 2 - t$ and $t$ are differently colored for $2 \le t \le n$ Moving $t$ through $2$ to $n$, and repeatedly using $(**)$ after working out the color for each number $t$ from the color of the number $2n + 2 - t$, we get that the numbers from $1$ to $n$ are R, and those from $n + 1$ to $2n$ are B. Then, $(2n + 1) + n = (n + 1) + 2n$ gives the required contradiction. Case 2 : $2n + 1$ is B. Then, $2n - 1$ is R by $(*)$ on $x = 2n$. Then, $2$ is B by $(**)$. Thus, $f(2n + 2) = f(2n) + f(2) = (2n + 2)c$. Thus, $2n + 2$ is R by $(*)$ on $x = 2n + 1$. Then, $(2n + 2) + 1 = (2n + 1) + 2$ gives a contradiction.

The answer is $k=3$. Let $(i)$ and $(ii)$ denote the two conditions in the statement respectively. Construction: $ f(n) = \begin{cases} \frac{10n}{3} & n\equiv 0 \pmod 3 \\ n & \text{else} \end{cases} $ We colour numbers $i \mod 3$ with colour $i$. Then it is easy to see that $(i)$ holds. Also $10=f(3) \neq f(2)+f(1)=3$, so $(ii)$ holds as well. Now it remains to prove that $\leq 2$ colors cannot work. Trivially, if we have just one color then $(ii)$ is never satisfied. Now assume we have two colors: red and blue. WLOG, $\textcolor{blue}{1}$ is blue. By setting $m=n$ in $(i)$, $f(2n)=2f(n) \ \ \forall n \in \mathbb{N} \dots (1)$. Take the smallest number $t$ such that $f(t) \neq tf(\textcolor{blue}{1})$. We cannot have $t$ even or else $f(t) =2f(\frac{t}{2}) = tf(\textcolor{blue}{1})$. Claim: $\forall l \in \mathbb{N_{\text{odd}}}$, $l < t$, $l$ and $t$ have different colors. AFSoC, there exists some odd $l<t$ with the same color as $t$. Since $\frac{l+t}{2}< t$, by $(1)$, $f(l+t) = 2f\bigg(\frac{l+t}{2} \bigg) = (l+t)f(\textcolor{blue}{1})$. By $(i)$, $(l+t)f(\textcolor{blue}{1})=f(l+t)=f(l)+f(t) = f(t) +lf(\textcolor{blue}{1}) \longrightarrow f(t)=tf(\textcolor{blue}{1})$. Contradiction. So by our claim, $\textcolor{red}{t}$ and $\textcolor{red}{2}$ are red. Now, $f(t+2)= f(\textcolor{red}{t})+f(\textcolor{red}{2}) = f(\textcolor{red}{t}) + 2 f(\textcolor{blue}{1}) \dots (2)$. Consider two cases, Case 1: $\textcolor{blue}{t+2}$ is blue. Since $\frac{t+3}{2} <\textcolor{red}{t}$ if $\textcolor{red}{t} >\textcolor{red}{3}$ then by $(1) \ \ f(t+3) = 2f\bigg(\frac{t+3}{2} \bigg) = (t+3)f(\textcolor{blue}{1})$ So by $(i),(2) \ \ (t+3)f(\textcolor{blue}{1})=f(t+3) =f(\textcolor{blue}{t+2}) +f(\textcolor{blue}{1})=f(\textcolor{red}{t})+3f(\textcolor{blue}{1}) \longrightarrow f(\textcolor{red}{t})=tf(\textcolor{blue}{1})$. Contradiction. Case 2: $\textcolor{red}{t+2}$ is red. So by $(1) \ \ f(2t+2) = 2f( t+1) = 4 f \bigg(\frac{t+1}{2} \bigg) = (2t+2)f(\textcolor{blue}{1})$, since $\frac{t+1}{2} <\textcolor{red}{t}$. By $(i) \ \ (2t+2)f(\textcolor{blue}{1}) =f(2t+2) = f(\textcolor{red}{t+2})+f(\textcolor{red}{t}) = 2f(\textcolor{red}{t}) + 2f(\textcolor{blue}{1}) \longrightarrow f(\textcolor{blue}{t}) = tf(\textcolor{blue}{1})$. Contradiction. Lastly, if $\textcolor{red}{t}= \textcolor{red}{3}$ then we need to re-consider case 1, i.e. $\textcolor{blue}{5}$ is blue. By $(1) \ \ f(6) = 2f(\textcolor{red}{3})$ So by $(i),(2) \ \ 2f(\textcolor{red}{3})=f(6) =f(\textcolor{blue}{5}) +f(\textcolor{blue}{1})=f(\textcolor{red}{3})+3f(\textcolor{blue}{1}) \longrightarrow f(\textcolor{red}{3})=3f(\textcolor{blue}{1})$. Contradiction. We are done.

We claim that the minimum such $k$ is $k = 3$. To see that this works, consider the function $f$ that has $f(x) = x$ when $3 \nmid x$ and $f(x) = x/3$ when $3 \mid x$. We then color the integers according to their residue modulo $3$. It is obvious that a coloring with $k = 1$ will not work, because then there will exist no $m$ and $n$ with $f(m) + f(n) \ne f(m+n)$. We will now show that there exists no satisfactory coloring and function with $k = 2$. Suppose there exists such a coloring. Without loss of generality, let the two colors be red and blue, and let $1$ be colored red. We will show that $nf(1) = f(n)$ for all $n$, which suffices to show that the satisfactory coloring and function does not work. We note that $f(1) = f(1)$ and $f(2) = 2f(1) = f(1)+f(1)$ because $f(1)$ is the same color as itself. We will now show that $f(3) = 3f(1)$. If $2$ was the same color as $1$, we would have that $f(3) = f(1) + f(2) = 3f(1)$. We note that $f(4) = 2f(2) = 4f(1)$, so if $3$ was the same color as $1$, we would have that $f(3) = 4f(1)-f(1) = 3f(1)$. So we suppose that both $2$ and $3$ are colored blue. Since $2f(3) = f(4+2)$, we would be done if we had that $4$ was the same color as $2$, so we may assume that $4$ is red. Then, we have that $f(4) + f(1) = 5f(1) = f(2) + f(3)$, forcing $f(3) = 3f(1)$. Now, we will use strong induction for the general case of $n$. Base Case: This is trivial. Induction Step: If $n$ is even, we are immediately done, since we have that $f(n) = 2f(n/2) = nf(1)$. So suppose that $n$ is odd. Let $n = 2m + 1$. If $2m$ was red, we would have that $f(n) = nf(1)$, so we suppose that $2m$ is blue. Since $f(2m+2) = 2f(m+1) = (2m+2)f(1)$, we would be done if $2m+1$ was red, since we would have that $f(2m+1) + f(1) = f(2m+2)$, so we suppose that $2m+1$ is blue. Now, we note that $2f(2m+1) = f(4m+2) = f(2m + (2m+2))$, so we may assume that $2m+2$ is red. This directly implies that $f(2m+3) = (2m+3)f(1)$. If $2$ is blue, we are immediately done then. So we suppose that $2$ is red, giving that $(2m+4)f(1) = f(2m+4)$. Then, we suppose that $3$ is red, and continue on in this way. But this must end at some point, since $2m$ is blue. Thus, we must have that $f(2m+1) = (2m+1)f(1)$, and so we are done. $\blacksquare$

I like this problem, quite a new idea imo. I took longer than I'd like to admit to find a construction for $k=3$. The answer is $k=3$. As a construction, color a positive integer red if it's $1 \pmod{3}$, blue if it's $2\pmod{3}$, and green if it's $0\pmod{3}$. Then let: $$f(n)=\begin{cases}n/3& n\equiv 0 \pmod{3}\\n& \text{otherwise},\end{cases}$$which can be verified to follow both requirements. Now I will prove $k<3$ is impossible. Clearly $k \neq 1$, so we only have to prove $k=2$ fails. Let a function $f: \mathbb{Z^+} \to \mathbb{Z^+}$ which follows the conditions in the problem be called colorful. Suppose some colorful function $f$ exists which satisfies the conditions for $k=2$, and let $c=f(1)$. Also color the integers with red and blue. Call a positive integer $k$ proportional if $f(k)=ck$; note that $1$ is proportional by construction. It is clear that there must exist some non-proportional integer, otherwise $f(x)=kx$ for some $k$ and there do not exist $m,n \in \mathbb{Z^+}$ such that $f(m+n) \neq f(m)+f(n)$. We begin with the following lemma: Lemma: For any positive integer $k$, then $k$ is proportional if and only if $2k$ is proportional. Proof: Observe that $k$ and $k$ are colored the same, so we have $f(2k)=2f(k)$. Then $f(2k)=2ck$ if and only if $f(k)=ck$, as desired. Also note that if $m$ is proportional and $n$ is not, and both have the same color, then $m+n$ is not proportional. Now let $m$ be the least positive integer which is not proportional. Note that $m$ must be odd, since if it's even then $m/2$ is not proportional. Also, we require $m \geq 3$, so write $m=2n+1$ where $n \in \mathbb{Z^+}$. WLOG, let $2n+1$ be colored red. Suppose we have $a,b$ such that $a+b=2n+1$. Since $a,b<2n+1$, both are proportional. As such, they cannot be the same color, otherwise $f(2n+1)=f(a)+f(b)=c(a+b)=c(2n+1)$ and $2n+1$ is also proportional. Now, suppose $2m+1$ is colored red, where $m<n$. Then $2f(m+n+1)=f(2(m+n+1))=f(2n+1)+f(2m+1)$. Since $2m+1$ is proportional but $2n+1$ isn't, it follows that $2(m+n+1)$ is not proportional and neither is $m+n+1$, but since $m+n+1<2n+1$ this is impossible. Hence all odd numbers less than $2n+1$ are blue, which forces all the evens to be red. Note that for any $1 \leq m\leq n$, we have $f(2m)+f(2n+1)=f(2(m+n)+1)$, so $2(m+n)+1$ is not proportional. This implies that none of $2n+3,2n+5,\ldots,4n+1$ are proportional. Further, by the lemma, all of $2n+2,2n+4,\ldots,4n$ are proportional. Now suppose that some even number $2k$ in $[2n+2,4n]$ is colored blue. Then $f(1)+f(2k)=f(2k+1)$, so $2k+1$ is porportional. But $2k+1$ is an odd number in $[2n+3,4n+1]$, so $2k+1$ is not proportional. Hence all of $2n+2,2n+4,\ldots,4n$ are colored red. Now, since $4n$ and $2$ are both red and proportional, we have $f(4n)+f(2)=f(4n+2)$, so $4n+2$ is also proportional, and hence by the lemma $2n+1$ is proportional too, but we previously defined $2n+1$ to not be proportional: contradiction. Hence no proportional integers exist, which was previously shown to be impossible. As such there are no colorful functions $f$ when $k=2$, which implies the desired result. $\blacksquare$

The answer is $k=3$. For a construction, color the numbers by mod 3, and $f(n)=n$ if $n$ is not a multiple of 3 and $f(n)=2n$ if $n$ is a multiple of 3. Now, consider if there are only two colors. Let $f(1)=c$. We will assume condition (i) and try to disprove condition (ii). Call a positive integer $n$ bad if $f(n)=cn$. By definition, 1 is bad. Clearly, by condition (i), the sum of two bad numbers of the same color is bad, and the differences of two bad numbers of the same color is also bad. Now, suppose FTSOC that a good number exists. Let the smallest good number be $g$. Claim: $g$ is the smallest number of its color. Suppose that a smaller number $s$ is the same color as $g$. Since $g$ is defined as the smallest good number, $s$ is bad. Then, $f(g)\neq cg$, but $f(s)=cs$, so $f(g-s)\neq c(g-s),$ so $g-s$ is good, contradiction since $g$ is the smallest good number. WLOG 1 is red. Then, $g$ must be the smallest blue number. However, this means that 1 and $g-1$ are both red and also bad, contradiction. Thus, all numbers are bad, so $f$ is linear, contradicting (ii). Hence, $k=2$ is not possible. Clearly, $k=1$ is not possible either, since then $f$ would be linear, hence the answer is $k=3.$

this problem should be erased from existence for mental health reasons . The answer is we have $k=3 \text{(three)}.$ colors, it as we will show. first We together may and will suppose that there are only $\text{two} (2)$ colors in this world. and, of course We are a weird persons. we should call this colors "1" and $"2"$ (of course, no confusion with the numbers 1 and $2!$! ) so we may first See that for any k we have $k,k$ is the same color. (so easy!!! like kindergarden!!) so Of course ,from this observations what we will is that \[f(2k)=2f(k),\]very easy things. Next What we will do is:set f(1)=c because we can!!! we are is very funny. then we Clearly see that $f(2)=2c.$and then what we can do:induct (look it up if you don "t know what that is. very advanced.). to show that the very simple and obvious f(n)=n must. and what we do: We only do it for odd $2n+1$ it is trivial for even so what We will get is that : consider any Pair "of" Num-bers 1+2k and 2n-2k. we can see that these Add to $2n+1$!! so we may suppose that 2n+1 has that f(2n+1) is not $c(2n+1).$because we want to make this numbers feel Special !! So,,,then we can Very easy (like a children) see that the Num-bers $1+2k$ and 2n-2k must be differnt Colors!!very easy. And since we only have this 2 $(two)$ colors, we may say (because we are powerful.we know everyhing) That the $2n+1$ is the same of these colors , as for example. 1+2k. however, as i will show now, This is very dumb (you are not paying attension enough). because then We will have that f(1+2k+2n+1)$=f(2n+1)+f(1+2k).$,but since we are Assuming. have that the right side is not Equal to $c(2n+1+1+2k),,$ since c(2n+1) is not f(2n+1),,,by our assumpsion.and Also we also get that also c(1+2k) is f(1+2k,,)for the same. but Now !! (the kool step!!!)we have that $c(1+2k+2n+1)=c(2k+2n+2.)$ (so hard right!!!you will say But! distribitive prpopoerty is For pre--schoolers!! we are too smart.) BUT!!! we have $f(2k+2n+2)=2f(k+n+1)$ by the easy things we have done before. But however!! now we see that $k+n+1<2n+1$ so by assumpsion We get That!! f(k+n+1)=c(k+n+1) So!!! f(1+2k+2n+1)=c(1+2k+2n+1)!!!!!! This is IMPOSSIBLE!!! So. we Cannot have 1+2k and 2n+1 are the same of colors. so 2n+1 Must be the same as the , ($2n-2k,$ which is Special to,because it is Even!!and so if we let $1$ have color 1 and 2 have color $2$ (we are not so dumb when we name!!) we will see. that all even less then 2n+1 will have color $2$ and all odd less then that have $1,$and also .$2n+1$ is have color 2. very Cool!!!you think the same! Ok so we are on next part now,, it was kind Of long, the last. so now this time we are considering The number,,,2n+2. (cool! $different!!$) so , of course we get $f(2n+2)=2f(n+1)$ (by our Kinder-garden lemma from earlier (scroll up). so , , first If we have 2n+2 has color $1$ then , $2n+3$ Will have $f(2n+3$)=c(2n+3),,$ BUT!! this is impossible, Since: we have $f(2n+1) \ne c(2n+1)$ and f(2)=2c$ (easy) And they are both color 2,, ¡¡¡Very illegals!!!and bad .So;; we will have to $2n+2$ is colored 2 (very strange collors, you think too,,,, right.) and since We also can get,2n is colored $2$ then We will have that:: f(4n+2)$=c(4n+2)$!! very cool. (since $f(2n)+f(2n+2)=f(4n+2)$, if you are not smart.) so Now, what we do...we look that $f(4n+2)=2f(2n+1)$ (like kindergarden,) But!!!! we get $c(2n+1)$ is not f(2n+1) so We cannot!!! have $2f(2n+1)=2c(2n+1)$=c(4n+2, )Very bad!!!! soWe will find, that, we must $f(2n+1)=c(2n+1)$!!! BUT THEN.! we see f(n)=nc $\text{for all}$ n. BUT THIS GOES AGAINST NUNMBER $(Ii),$very Bad!!! SO, what we get has that we need More than just TWO colors!!!!!COOL!!!!! HI Aops user Megarine!!! so now We will have 3 (three) colors,this is very easy like kids. we simply look At the mod 3 (remainders if you is elementary schools and am not smart enough (like me and my big brain,,))). so if We take all of the 0 mod $3$ and make it so $f(x)=x/3$ when x is $0 \mod$ 3. (like discrimiation for numbers!! but this is not The "round table." so we Will not get into those thing here on this very Intelligents forums and people with big brain.) and then we have f(x)=x (you will say boring !! plain!! but this is A math forum, very respected, not a kids colorings, please bee mature.)so We See THat:we now neeed some coloring (maybe we are kids!!This is fun!math is wierd and we are alll kids. ) And of course you are not dumb (unless you are dumb) and you see that: there is Very easy a coloring:Just color it by its mod (remainder,,, for elementer school people).we chek thtat this works:since if Our twoo number are Both not 0 (mod $3)$ and same color::then : their sum will also be not 0 mod ($3)$ and will work,very trivial (easy) if your vocabulery is not strong (like mine). and off course:if Both are $(0)$ mod 3 and (of course will be same colour.) then weget of cours their sum wilwork tooo . . And:we dont want to fail the $(ii)$ like i failed My english test,,so what we do:its very easy We can just check:let $m=1$ And:n=2. Then:f(m$+n=)$f(3)$=1$ BUT!!f(m)$+f(n$)=1+2$=3$ !!!! COOL!!! SO,we are done It is very hard,difficult. BUT not for me Because i am Smart and big brain (see above Like i have said,, because i am so smart!!) THANks for reading And i hope That you have learned from this Beautiful solution and easy problem,,ok Now by guys i have more trivial Problems to do. $\boxed{}$ Aops-sherrif Please do not delete!! I worked $\text{Very}$ hard on this beautifull solucion!!I hope you will take time to understaned this,for what it is (a beautiful solution) and not what it might Look like (not a beautiful solution) Thanks.!

Note that $k = 1$ obviously doesn't work because then condition (i) implies Cauchy. Also note that $k = 3$ works by coloring the integers red, blue, and green when the residues are $0$, $1$, and $2$ modulo $3$, respectively, and then using the function where $f(n) = 2n$ if $n$ is red, and $f(n) = n$ otherwise. Now, it suffices to show that $k = 2$ fails. WLOG let $f(1) = 1$, and let the color be blue. Then we can easily get that $f(2n) = 2f(n)$ for any positive integer $k$. Call integers $m$ where $f(m) = m$ good, and bad otherwise. Take the minimal $x$ such that $x$ is bad. From the minimality, then we must have that $x$ is odd; otherwise, then $f(x) = 2f(x/2) = x$. Thus, let $x = 2n+1$ for a positive integer $n$. Claim: we have that $2n+1$ must be red. Proof: Assume otherwise. Then $f(2n+2) = f(2n+1) + f(1) \neq 2n+2$, but $f(2n+2) = 2f(n+1) = 2n+2$, contradiction. $\square$ Claim: Any reds below $2n+1$ must be even. Furthermore, all evens below $2n+1$ must be red. Proof: Assume that a red could be odd. Then for $y \leq n-1$, $f(2n+1) + f(2y+1) = f(2n+2y+2) = 2f(n+y+1) = 2n+2y+2$, because $n+y+1 \leq 2n$. But this implies $2n+1$ is good, contradiction. For the second part, note that all odds must be blue. Then if an even $e$ was also blue, we could find an odd $o$ such that $e + o = 2n+1$, which would also imply $2n+1$ is good, contradiction. $\square$ So now we have that $2n$ and $2n+1$ are red. Then $f(4n+1) = f(2n+1) + f(2n) \neq 4n+1$, so $4n+1$ is bad. Claim: All evens from $2n+2$ to $4n$ must be red. Note that they also happen to be good. Proof: We know the evens are good (since $f(2m) = 2f(m) = 2m$ as $m \leq 2n$). But for any even $e$, if it is blue, we can find an odd $o$ below $2n$ such that $o+e=4n+1$; in particular, this $o$ must also be blue and good. But then $f(4n+1) = f(o + e) = f(o) + f(e) = o + e = 4n+1$, contradiction. $\square$ Now, note that $4n+2$ is bad, as $f(4n+2) = 2f(2n+1) \neq 4n+2$. However, since all the evens up to $4n$ are red and good, then $f(4n+2) = f(2) + f(4n) = 4n + 2$, contradiction. Thus, $f(n) = n$ for all $n$ when $k = 2$. $\blacksquare$

A construction when $k=3$ is \[f(x) = \begin{cases} x & x \equiv 1,2 \pmod 3 \\ 2x & x \equiv 0 \pmod 3. \end{cases}\] We aim to show a contradiction for $k=2$, as $k=1$ clearly fails. Substituting $m=n$ gives the identity $f(2n)=2f(n)$, which also implies $f(2^kn)=2^kf(n)$. We then show $f(3n)=3f(n)$, which can be proven by exhausting all cases of shared colors: \begin{align*} (n,2n) &\implies f(3n) = f(n)+f(2n) = 3f(n) \\ (n, 3n) &\implies 4f(n) = f(4n) = f(n)+f(3n) \implies f(3n) = 3f(n) \\ (2n,4n) &\implies 2f(3n) = f(4n)+f(2n) = 6f(n) \implies f(3n)=3f(n) \\ (n,4n) + (2n,3n) &\implies f(n)+f(4n)=f(2n)+f(3n) \implies f(3n)=3f(n). \end{align*} Our desired contradiction can be obtained from showing $f$ is linear, or $f(x)=x \cdot f(1)$, which violates the second condition. Suppose $k$ is the least positive integer such that $f(k) \neq k \cdot f(1)$. In order words, all $j<k$ satisfies $f(j)=j \cdot f(1)$. Note $k$ cannot be even, or $\frac k2$ is a smaller value which also holds. We again proceed with casework: \begin{align*} \left(k, \frac{k-3}{2}\right) &\implies f(k) + f\left(\frac{k-3}{2}\right) = 3 f\left(\frac{k-1}{2}\right) \implies f(k) = k \cdot f(1) \\ \left(k, \frac{k+3}{2}\right) &\implies f(k) + f\left(\frac{k+3}{2}\right) = 3 f\left(\frac{k+1}{2}\right) \implies f(k) = k \cdot f(1) \\ \left(\frac{k-3}{2}, \frac{k+3}{2}\right) &\implies f\left(\frac{k-3}{2}\right) + f\left(\frac{k+3}{2}\right) = k \cdot f(1). \end{align*} Each results in a contradiction, which finishes, giving our answer of $k=\boxed{3}$. $\blacksquare$

Surprisingly difficult for EGMO2, in my opinion. The answer is $k=3$; construction is given by coloring the integers mod $3$ and picking $f(n) = 100n$ when $n \equiv 0 \pmod 3$ and $f(n) = n$ otherwise. To see the bound, we will show that $f$ is linear via induction on $n$. In particular, let $f(1) = k$; we will show that $f(n) = nk$ for all $n$. First, observe that if $f(2n) = 2f(n)$ for any $n$; hence, $f(2) = 2k$, which completes the base case. For the inductive step, assume that $f(a) = ak$ for all $a < n$ for some odd $n$. (The case for even $n$ is vacuous.) Now, If there exist two $a, b \leq n$ such that $a$ and $b$ are the same color and $a+b = n$, then it trivially follows that $f(n) = nk$. If for all $a, b \leq n$ such that $a+b=n$, $a$ and $b$ are opposite colors, suppose $a < b$ and $a$ is colored red, $b$ blue. Then, $2a$ and $2b$ must also be colored differently. We have two subcases: If $2a$ is blue and $2b$ is red, then $f(2a+b) = (2a+b)k$ and $f(a+2b) = (a+2b)k$. Then, if $n=a+b$ is blue, then $f(b) + f(n) = f(a+2b)$, fixing $f(n)$. Otherwise, $f(a)+f(n) = f(2a+b)$, also fixing $f(n)$. If $2a$ is red and $2b$ is blue, then assume for the sake of contradiction that $f(n) \neq kn$. It follows that $b-a$ must be blue, and as $(b-a)+(a+b) = 2b$, $n=a+b$ must be red. Now, I claim that there must exist some odd $i < n$ that is colored red. Suppose otherwise. Then all odd $i < n$ are colored blue, and by assumption all of the even $j < n$ must be colored red. But because the second case must hold true for all $a + b = n$, it follows that $a$ and $a/2$ are colored identically for any $a < n$, which contradicts this assumption. Hence, pick some odd $i< n$ that is colored red, and notice that $f(i)+f(n) = f(2j)$ for some $j < n$. As $f(i) = ki$ and $f(2j) = 2jk$ are known, it follows $f(n) = nk$ nonetheless. Thus $f$ is linear when $k=2$, which violates the second assumption.

why doesn't just color 1 red and all the others all blue and stating f(x) = x for x>= 2 and f(1) = 100 not work?

David_Kim_0202 wrote: why doesn't just color 1 red and all the others all blue and stating f(x) = x for x>= 2 and f(1) = 100 not work? It is stated that $m, n$ not necessarily distinct, so $f(1 + 1) = 2f(1) = 200$ but this contradicts $f(2)=2$

I claim that we need at least $k=3$ colors. First, the construction. The function \[ f(x) = \begin{cases} x & x\equiv 1 \pmod 3 \\ x & x\equiv 2 \pmod 3 \\ 2x & x\equiv 0 \pmod 3 \\ \end{cases} \]with all numbers $1$ mod $3$ colored purple, all numbers $2$ mod $3$ colored green, and all numbers $0$ mod $3$ colored blue works. We prove this by taking this into cases by condition. The first condition is that $f(m+n)=f(m)+f(n)$ if $m$ and $n$ are the same color. If $m$, $n$ are both $1$ mod $3$, we have that \[f(m)+f(n)=m+n=f(m+n),\]since $m+n$ is $2$ mod $3$. Similarly, if $m$ and $n$ are both $2$ mod $3$, we get that \[f(m)+f(n)=m+n=f(m+n),\]since $m+n$ is $1$ mod $3$. Finally, if $m$ and $n$ are both $0$ mod $3$, then we get that \[f(m)+f(n)=2m+2n=f(m+n),\]since $m+n$ is $0$ mod $3$. This proves that this function satisfies the first condition. Now, for the second condition, we have that \[f(3)=6,\]and \[f(1)+f(2)=1+2=3,\]meaning that $\exists m,n$ s.t. $f(m)+f(n)\neq f(m+n)$. -- Now I claim that at most two colors doesn't work. Let these two colors be green and purple. First, note that \[f(m)+f(m)=f(2m) \implies 2f(m)=f(2m),\]since $f(m)$ and $f(m)$ must be the same color. This means that \[f(2)=2f(1).\]Now, for inductive purposes, let us assume that \[f(x)=xf(1),\]for all $1\leq x\leq 2k$ for some integer $k\geq 1$. I claim that $f(2k+1)=(2k+1)f(1)$ and $f(2k+2)=(2k+2)f(1)$. WLOG, let $f(2k+1)$ be green and FTSOC assume that $f(2k+1)\ne(2k+1)f(1)$. Now, note that if $f(2k-1)$ is green, we would have that \[4kf(1)=2(2kf(1))=2f(2k)=f(4k)=f(2k-1)+f(2k+1) \implies f(2k+1)=(2k+1)f(1),\]since $f(2k-1)=(2k-1)f(1)$. This is clearly a contradiction, meaning that $f(2k-1)$ must be purple. Similarly, we have \[f(2)+f(2k-1)=(2+(2k-1))f(1)=(2k+1)f(1),\]which can't possibly be $f(2+(2k-1))=f(2k+1)$. This means that $f(2)$ and $f(2k-1)$ must be different colors, meaning that $f(2)$ has to be green. Now, note that if $f(2k+3)$ is green, we get that \[f(4k+4)=f(2k+1)+f(2k+3)=f(2k+1)+f(2k+1)+f(2),\]since $f(2)$ is green. This implies that \[(4k+4)f(1)=4f(k+1)=2f(2k+2)=f(4k+4)=2f(2k+1)+f(2)=2f(2k+1)+2f(1),\]meaning that $f(2k+1)$ must be $(2k+1)f(1)$, a contradiction. Therefore $f(2k+3)$ must be purple. If $f(2k+3)$ is purple, then we have that \[2f(2k+1)=f(4k+2)=f(2k+3)+f(2k-1)=f(2k+1)+f(2)+f(2k-1),\]\[\implies f(2k+1)=f(2)+f(2k-1)=2f(1)+(2k-1)f(1)=(2k+1)f(1),\]since $f(2k-1)$ is also purple. This is again a contradiction, meaning that $f(2k+1)$ must be $(2k+1)f(1)$. Finally, we also get that \[f(2k+2)=2f(k+1)=2(k+1)f(1)=(2k+2)f(1),\]completing our inductive step. This then yields that \[f(x)=xf(1),\]for all integers $x$. This means that there do not $\exists m$, $n$ s.t. $f(m+n)\neq f(m)+f(n)$, a contradiction to the problem conditions. Therefore there must be at least three colors, finishing the problem.

Rare Merlijn L The answer is $k=3$, attained by the function $f(x) = x$ when $3 \mid x$ and $f(x) = 2x$ otherwise. To prove that $k=2$ is impossible, it suffices to show that any function which satisfies the first condition is of the form $f(x) = cx$. Let $r$ be the largest integer such that $1, 2, \dots, r$ are all colored the same color, say, red, while $r+1$ is colored blue. We will now prove that $f(x) = cx$ by strong induction on $x$: Base case: $f(x) = cx$ for $x = 1, 2, \dots, 2r$, by applying the first condition on any two of $1, 2, \dots, r$. Inductive step: To show $f(x) = cx$, we split into cases: If $x$ and $x-1$ are both red, then $f(x) = f(x-1) + f(1) = cx$. If $x$ is red and $x-1$ is blue, then \[f(x) + f(r) = f(x+r) = f(x-1) + f(r+1),\]so $f(x) = cx$. If $x$ is blue, let $y$ be the largest integer less than $x$ for which $y$ is red. We split into further cases: If $y < x-r-1$, we have $f(x) = f(x-r-1) + f(r+1)$. If $y \geq x-r$, we have $f(x) = f(y) + f(x-y)$. If $y = x-r-1$, we split into further cases: If $x+1$ is blue, we have \[2f(x) = f(x-1) + f(x+1) = f(x-1) + f(r+1) + f(x-r),\]so $f(x) = cx$. If $x+1$ is red, we have \[f(x) + f(r+1) = f(x+r+1) = f(x+1) + f(r) = f(x-r) + f(r+1) + f(r),\]so $f(x) = cx$.

We will show that the answer is $3$. Here is the construction (color the integers modulo $3$) \[f(n)=\begin{cases} f(n)=1434n & n\equiv 0 \pmod 3\\ f(n)=n & \text{else} \end{cases}\] Now suppose the problem is true for 2 colors. We will prove that $f$ is linear. Let $f(1)=a$. I claim that $f(n)=an$ and we proceed by induction. Suppose that $f(1)=a$, $f(2)=2a$, $\dots$, $f(2n)=2na$ and let \[g(n)=\begin{cases} 1 &n\text{ is red}\\ 0 &n\text{ is blue} \end{cases}\] Let $S=\{k | f(k)=ka\}$. We clearly have $f(2n+2)\in S$ and assume for contradiction that $2n+1\not\in S$. We will spam the fact that if $g(2n+1)=g(k)$ then at least one of $k$ and $2n+1+k$ isn't in $S$. It's not hard to see that $2n+4$, $2n+6$, $\dots$, $4n$ are all in $S$ so $g(2n+1)\neq g(k)$ for all $k\in\{1,3,\dots,2n-1\}$, hence \[g(1)=g(3)=\dots=g(2n-1)\neq g(2n+1)\] Also notice that $g(1)\neq g(2n)$, $g(2)\neq g(2n-1)$, $\dots$, $g(n)\neq g(n+1)$ so \[g(2)=g(4)=\dots=g(2n)=g(2n+1)\] It's also not hard to see that $g(2n+2)=g(2n+1)$. Now $2n+3\in S$ and look at $g(2n+3)$. If $g(2n+3)=g(2n+1)$, then $2n+5\in S$ so $2n+1\in S$, which is a contradiction, hence $g(2n+3)=g(1)$. Now we get $4n+2\in S$ so $2n+1\in S$, a contradiction. This completes the induction, hence $f$ is linear so it can't satisfy the second property. $\blacksquare$

Answer is $k=3$ with construction $f(x)=2x$ when $3 \mid x$ and $x$ otherwise. Coloring based on residue modulo $3$. We will prove that $k=2$ is impossible. Let the minimum value of $x$ such that $f(x) \neq xf(1)$ be $2a+1$. This must be odd because $2f(x)=f(2x)$ so if this value is even we can keep dividing by $2$ until we can't anymore. Define the function $C(x)$ to be the color of $x$. Observe that for all $x,y >0$ such that $x+y=2a+1$ then $C(x) \neq C(y)$. Now observe $$f(2a+2) = 2f(a+1)= 2(a+1)f(1) \neq f(1) + f(2a+1) $$$$f(2a+4)=2(a+2)f(1) \neq f(3)+f(2a+1)$$$$\vdots$$$$f(4a)=4af(1) \neq f(2a-1)+f(2a+1)$$$$\implies C(2a+1) \neq C(1) = C(3) = C(5) = \cdots = C(2a-1)$$$$C(2a+1)=C(2)=C(4) = \cdots = C(2a) $$$$f(2a+3)=f(2)+f(2a+1) = 2f(1)+f(2a+1)$$$$f(2a+2)=2f(a+1)=2(a+1)f(1)$$$$f(2a+2)+f(1) = (2a+3)f(1) \neq 2f(1)+f(2a+1) = f(2a+3)$$$$\implies C(2a+2) \neq C(1)$$Now $$2f(2a+1) = f(4a+2)=f(2a+2)+f(2a)= (4a+2)f(1) \implies f(2a+1)=(2a+1)f(1)$$A contradiction and also I just lost the game buh.

We claim the answer is $\boxed{k = 3}$. Construction: We define $f(n) = 0$ for $n \equiv 0 \pmod{3}$ and $n$ for all other $n$, which satisfies both conditions. Proof that lower values don't work We prove by induction that $f(x) = xf(1) \forall x$ if we use only two colors, no matter what. First notice the fact that $f(2x) = 2f(x)$, now we'll jump into the proof. Base Case: $f(1) = 1f(1)$ by definition. Now note that if we have $f(x) = xf(1) \forall x \le 2a-1$, then automatically $f(2a) = 2f(a) = 2af(1)$, so we're done. Otherwise, we have $f(x) = xf(1) \forall x \le 2a$, with the goal of proving $f(2a+1) = (2a+1)f(1)$. For now, we assume WLOG the numbers are colored blue and red and that $2a+1$ is colored red. We write $n = B$ if n is blue and $n = R$ otherwise. Assume FtSoC the thing to be proven isn't true. Note that if any one of the pairs $\{k, 2a-k+1\}$ has monochromatic elements, then it's a clear contradiction, so in fact all of these sets have heterochromatic elements. Further, we claim that $\forall a \le 2n$, $n = B$ iff $n$ is odd. Note that for odd $b < 2n$ if $b = R$, then $f(b) + f(2a+1) = f(2a+b+1) = 2f\left(a+\frac{b+1}{2}\right) = (2a+b+1)f(1),$ a contradiction. So indeed $b = B$ and thus all odds which can be written as $2a+1-b$ are red. Now we take cases on the color of $4a$. Case 1: $4a$ is blue. Then we have $$f(4a) + f(1) = f(2a+1) + f(2a) \implies f(2a+1) = (2a+1)f(1).$$ Case 2: $4a$ is red. Then we have $$f(4a)+f(2) = 2f(2a+1) \implies f(2a+1) = (2a+1)f(1).$$ Thus in all cases we have a contradiction, and $f(2a+1) = (2a+1)f(1)$, completing the induction, and thus the proof. $\square$