Problem 4

Prove that there is no function

f

from the set of non-negative integers into itself such that

f(f(n)) = n + 1987

for every non-negative integer

n

Step 1 of 5: First prove f is injective

Previous step Next step

In plain words

Applying $f$ twice recovers the input up to the same translation, so two inputs with the same first image must already have been equal.

f(f(m))=f(f(n))\implies m+1987=n+1987\implies m=n

Detailed analysis

If $f(m)=f(n)$ , applying $f$ to both sides gives $f(f(m))=f(f(n))$ . The assumed equation then yields $m+1987=n+1987$ , hence $m=n$ . Thus $f$ is injective.