XXXI Brazilian Math Olympiad

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⟹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⟹f(n)=n+1$. Now if $n<-1$ we have $2009n+2008<n$; for example, $2009c+2008<c$. Then $f(2009c+2008)=2009f(c)⟺2009c+2009=2009f(c)⟺f(c)=c+1$. Finally, from $2009(c+1)+2008<c+1⟹2009(c+1)+2008\le c$ we have $f(2009(c+1)+2008)-2009f(c+1)⟺f(c+1)=c+2$. But $f(c+1)=0$, so $c=-2$. So we have a third solution $$f(n)=\{\begin{array}{ll}n+1,& \text{if }n<0\\ 0,& \text{if }n\ge 0\end{array}$$ It can be easily verified that this solution also satisfies the required conditions.