IMO 1996 SL A8

Origin: ROM | Category: Algebra

Problem

Let $\mathbb{N}_0$ denote the set of nonnegative integers. Find all functions $f:\mathbb{N}_0 \to \mathbb{N}_0$ such that

$$f(m + f(n)) = f(f(m)) + f(n), \quad \forall m,n \in \mathbb{N}_0.$$

Solution

Putting $m=n=0$ we obtain $f(0)=0$ and consequently

$$f(f(n)) = f(n)$$

for all $n$. Thus the given functional equation is equivalent to

$$f(m + f(n)) = f(m) + f(n), \quad f(0)=0.$$

Clearly one solution is $\forall x, f(x)=0$. Suppose $f$ is not the zero function. We observe that $f$ has nonzero fixed points (for example, any $f(n)$ is a fixed point). Let $a$ be the smallest nonzero fixed point of $f$. By induction, each $ka$ $(k \in \mathbb{N})$ is a fixed point too. We claim that all fixed points of $f$ are of this form. Indeed, suppose that $b = ka + i$ is a fixed point, where $i<a$. Then

$$b = f(b) = f(ka + i) = f(i + f(ka)) = f(i) + f(ka) = f(i) + ka;$$

hence $f(i)=i$. Hence $i=0$.

Since the set of values of $f$ is a set of its fixed points, it follows that for $i=0,1,\dots,a-1$,

$$f(i) = a n_i$$

for some integers $n_i \ge 0$ with $n_0=0$. Let $n = ka + i$ be any positive integer, $0 \le i < a$. As before, the functional equation gives us

$$f(n) = f(ka + i) = f(i) + ka = (n_i + k)a.$$

Besides the zero function, this is the general solution of the given functional equation. To verify this, we plug in $m=ka+i$, $n=la+j$ and obtain

$$f(m + f(n)) = f(ka + i + f(la + j)) = f((k + l + n_j)a + i) = (k + l + n_j + n_i)a = f(m) + f(n).$$