IMO 1987 - function such that $f(f(n))=n+1987$

Here is an alternative approach. It is obvious that such an $f$ must be an injection. Now, look at sets $\mathbb{N}$, $A = f(\mathbb{N})$ and $B = f(f(\mathbb{N})) = \{n + 1987 \ | \ n \in \mathbb{N}\}$.

It is easy to see that $B \subset A \subset \mathbb{N}$, and also from the injectivity of $f$ that $f$ induces a bijection between the disjoint sets $\mathbb{N} \setminus A$ and $A \setminus B$. Therefore, $\mathbb{N} \setminus B = (\mathbb{N} \setminus A) \cup (A \setminus B)$ must contain an even number of elements. But $|\mathbb{N} \setminus B| = 1987$, which is a contradiction, and we are done.

Here is a generalisation.

Proposition. For positive integers $k,l$, the functional equation $$ f^k(n)=n+l\qquad\text{for all $n$} $$ has no solutions $f$ in the functions $\Bbb Z\to\Bbb Z$, or in the functions $\Bbb N\to\Bbb N$, unless $k$ divides $l$.

In the case $k\mid l$, one does of course have solutions, for instance $n\mapsto n+l/k$.

Proof. Assume that $f$ satisfies the functional equation.

• For all $n$ one has $f(n+l)=f^{k+1}(n)=f(n)+l$.
• Therefore $f(n+l)-(n+l)=f(n)-n$, and $f(n)-n$ is constant when $n$ varies over any congruence class modulo $l$.
• The image under $f$ of such a congruence class is therefore another congruence class, and $f$ gives rise to a function $\bar f:\Bbb Z/l\Bbb Z\to\Bbb Z/l\Bbb Z$.
• Since $(\bar f)^k(\bar n)=\bar n$ for all $\bar n\in\Bbb Z/l\Bbb Z$, this function $\bar f$ is a bijection.
• Put $S=\sum_{i=0}^{l-1}(f(i)-i)$; note that since $f(i)-i$ is constant on congruence classes modulo $l$, the same sum is obtained if one sums over a different set of representatives of the congruence classes modulo$~l$.
• In particular, since for any $j\in\Bbb N$ the set $\{\,f^j(i)\mid0\leq i<l\,\}$ is a set of representatives of the congruence classes modulo$~l$ (since $(\bar f)^j$ is a bijection), one has $\sum_{i=0}^{l-1}(f^{j+1}(i)-f^j(i))=S$.
• Also $\{\,f(i)\mid0\leq i<l\,\}$ is set of representatives of the congruence classes modulo$~l$, so $\sum_{i=0}^{l-1}f(i)\equiv\sum_{i=0}^{l-1}i\pmod l$, and hence $S\equiv0\pmod l$. So $S=ls$ for some integer$~s$.
• From the functional equation $\sum_{i=0}^{l-1}\bigl(f^k(i)-i\bigr)=\sum_{i=0}^{l-1}l=l^2$.
• One can decompose each term in that sum as a telescopic sum: $f^k(i)-i=\sum_{j=0}^{k-1}\bigl(f^{j+1}(i)-f^j(i)\bigr)$.
• Therefore $$l^2=\sum_{i=0}^{l-1}\bigl(f^k(i)-i\bigr) =\sum_{j=0}^{k-1}\sum_{i=0}^{l-1}(f^{j+1}(i)-f^j(i)\bigr) =\sum_{j=0}^{k-1}S=kS=kls.$$
• Simplifying by a factor $l$ one gets $l=ks$, proving that $k$ divides $l$.

Hint $\ $mod $\rm\,p\!:\ f(f(n)) = n+p\equiv n\:$ is an involution, hence $\rm\:p\:$ odd $\Rightarrow$ that it has a fixed point $\rm\:f(n)\equiv n,\:$ so $\rm\:f(n) = n\!+\!k p,\ k\in\Bbb Z.\:$ Now the orbit of $\rm\:f\:$ on $\rm\,n\,$ yields a contradiction

$$\rm\begin{array}{rlcl} &\rm n &\rm \to &\rm \color{#C00}{n+kp} \\ \to &\rm \color{#0A0}{n\!+\!p} &\rm \to &\rm n\!+\!(k\!+\!1)p \\ \to &\rm n\!+\!2p &\rm \to &\rm n\!+\!(k\!+\!2)p\\ \to &\rm n\!+\!3p &\rm \to &\rm n\!+\!(k\!+\!3)p\\ &\rm\ \cdots &\rm &\rm \quad\cdots \\ \to &\rm \color{#C00}{n\!+\!kp} &\rm \to &\rm n\!+\!(k\!+\!k)p = \color{#0A0}{n\!+\!p}\ \Rightarrow\ 2k=1\ \Rightarrow\Leftarrow\: k\in\Bbb Z\\ \end{array}$$

Remark $\ $ This was a hint I posted many years ago in another math forum. You can find many further posts here exploiting parity and involutions by searching on involution and Wilson (group theoretical form of Wilson's theorem).