Problem 1803

If $f$ is injective, then $f(f(n)) = f(n+1)$ reduces to $f(n) = n+1$, one of the solutions, another solution is $f(n) = 0$ for all $n \in \mathbb{Z}$. So suppose $f$ is neither injective nor identically zero. So there are two integers $a < b$ such that $f(a) = f(b)$. By applying (i) we obtain $f(a+1) = f(f(a)) = f(f(b)) = f(b+1)$ and one can deduce by induction that $f(a+n) = f(b+n)$, i.e., $f(n)$ is periodic for $n \ge a$ and therefore bounded.

We will prove that $f(n) = 0$ for $n \ge -1$. Suppose the contrary and let $k \ge n$ be such that $f(k) = M$ has maximum absolute value. By (ii), $|f(2009k + 2008)| = |2009f(k)| = 2009|M|$. So either $n > 2009k + 2008 \ge 2009n + 2008 \implies n < -1$ or $M = 0$. Since $n \ge -1$, $M = 0$ and so $f(N) = 0$ for all $N \ge n$, and in particular $f(n) = 0$.

Now suppose that there exist $a < b$ such that $f(a) = f(b) \ne 0$. Then, again by the argument above $f(n)$ is periodic for $n \ge a$ and so $f(a) = f(b) = 0$, a contradiction. So if $f(a), f(b) \ne 0$ then $f(a) \ne f(b)$.

Now we will prove that the set of negative integers $t$ such that $f(t) = 0$ is finite. Suppose it's not, so for every integer $k$ there is an integer $r$ such that $f(r) = 0$ and $r < k$. By applying (i) repeatedly just like before we prove that $f(n) = 0$ for all $n \ge r$; in particular $f(k) = 0$, and the function is identically zero. So there is an maximum integer $c$ such that $f(n) \ne 0$ for all $n \le c$. Since $f$ is injective in $\mathbb{Z} \cap ]-\infty, c[$, for $n < c$ we have $f(f(n)) = f(n+1) \ne 0 \implies f(n) = n+1$. Now if $n < -1$ we have $2009n+2008 < n$; for example, $2009c+2008 < c$. Then $f(2009c+2008) = 2009f(c) \iff 2009c + 2009 = 2009f(c) \iff f(c) = c+1$. Finally, from $2009(c+1) + 2008 < c+1 \implies 2009(c+1) + 2008 \le c$ we have $f(2009(c+1)+2008)-2009f(c+1) \iff f(c+1) = c+2$. But $f(c+1) = 0$, so $c = -2$. So we have a third solution
$$f(n) = \begin{cases} n+1, & \text{if } n < 0 \\ 0, & \text{if } n \ge 0 \end{cases}$$
It can be easily verified that this solution also satisfies the required conditions.