1996 IMO Problems/Problem 3

Problem

Let $S$ denote the set of nonnegative integers. Find all functions $f$ from $S$ to itself such that

$f(m+f(n))=f(f(m))+f(n)$ $\forall m,n \in S$

Solution

Plugging in m = 0, we get f(f(n)) = f(n) $\forall n \in S$ . With m = n = 0, we get f(0) = 0.

If there are no fixed points of this function greater than $0$ , then $f(x) = 0 \forall x \in \mathbb{N}$ , which is a valid solution.

Let $n_{0}$ be the smallest fixed point of $f(x)$ such that $n_{0} > 0$ . $\implies f(n_{0}) = n_{0}$ . Plugging $m = n = n_{0}$ , we get $f(2n_{0}) = 2f(n_{0})$ .

By an easy induction, we get $f(kn_{0}) = kf(n_{0}) \forall k \in \mathbb{N}$ .

Let $n_{1}$ be another fixed point greater than $n_{0}$ . Let $n_{1} = qn_{0} + r$ , where $r < n_{0}$ .

So, $f(n_{1}) = f(qn_{0} + r) = f(r + f(qn_{0})) = f(r) + qn_{0} = r + qn_{0}$ .

$\implies f(r) = r$ . But, $r < n_{0} \implies r = 0$ . This means that the set of all fixed points of $f(x)$ is ${0, n_{0}, 2n_{0}, 3n{0}, ...}$ .

Let $x < n_{0}$ and $f(x) = b$ . So, $b = f(x) = f(f(x)) = f(b)$ . So, $b$ is also a fixed point, which means that the functional values of non-fixed points are permutations of the fixed points. So let $f(k) = a_{k}n_{0}$ , where $a_{k} \in \mathbb{N}$ .

Now let $n = qn_{0} + r$ , where $r < n$ . So $f(n) = f(qn_{0} + r) = f(r + f(qn_{0})) = f(r) + f(qn_{0}) = f(r) + qn_{0} = a_{r}n_{0} + qn_{0} = n_{0}\dot(a_{r} + q)$ . So there are two general solutions, $f(x) = 0$ (where the only fixed point is 0) or $f(x) = n_{0}\dot(a_{r} + q)$ where $n_{0}$ is the smallest fixed point greater than 0 (in the second case), $f(r) = a_{r}n_{0}$ and q is the quotient when $n$ is divided by $n_{0}$ .

1996 IMO (Problems) • Resources
Preceded by Problem 2	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 4
All IMO Problems and Solutions

Page

Toolbox

Search

1996 IMO Problems/Problem 3

Problem

Solution

See Also