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 4 of 5: The two pieces partition exactly 1987 elements

Previous step Next step

In plain words

The second iterate misses exactly the first 1987 nonnegative integers, and A and B divide those misses into alternating layers.

A\cap B=\varnothing,\qquad A\cup B=\mathbb N_0\setminus f(f(\mathbb N_0))=\{0,1,\ldots,1986\}

Detailed analysis

The sets $A$ and $B$ are disjoint: $A$ is outside $f(\mathbb N_0)$ , whereas $B\subseteq f(\mathbb N_0)$ . Their union is the complement of $f(f(\mathbb N_0))$ , because $A$ is the complement of $f(\mathbb N_0)$ and $B$ is the part of $f(\mathbb N_0)$ outside $f(f(\mathbb N_0))$ . The functional equation gives $f(f(\mathbb N_0))=\{n+1987:n\ge0\}=\{1987,1988,\ldots\}$ , so the union is $\{0,1,\ldots,1986\}$ , of size $1987$ .