, 2021

All the solutions are $f: \mathbb{N} \to \mathbb{N}$ such that $f(x) \in \{x, x+1\}$, $\forall x \in \mathbb{N}$. Note that in this case, we have $\|f(x) - x\|_* = 0$ so they are clearly solutions.

Now we show that these are all the solutions. In fact, if there exists an $x \in \mathbb{N}$ such that $f(x) \notin \{x, x+1\}$, then we have that $\|f(x) - x\|_* \neq 0$. Thus we can find a minimum $s \in \mathbb{N}$ such that $f^s(x) = x$. By the minimality of $s$, we have $s \mid \|f(x) - x\|_*$. Note that we also have that $s$ is the minimum such that $f^s(f(x)) = f(x)$, showing that $s \mid \|f^{(2)}(x) - f(x)\|_*$. By induction, we then have $s \mid \|f^{(i+1)}(x) - f^{(i)}(x)\|_*$. Let $a_i = f^{(i+1)}(x) - f^{(i)}(x)$. Then since $f^{(s)}(x) = x$, we have that $a_0 + a_1 + \cdots + a_{s-1} = 0$. We also have that $\|a_0\|_* + \|a_1\|_* + \cdots + \|a_{s-1}\|_*$ is divisible by $s$. However, by the definition of $\|\cdot\|_*$, we know that $\|x\|_* = x$ if $x \le 0$, and $\|x\|_* = x-1$ if $x \ge 1$. Since $\|a_0\|_* \neq 0$ by assumption, we know that either $a_0 > 1$ or $a_0 < 0$. In the first case, we know that there exists an $a_i$ such that $a_i < 0$. In the second case, we know that there exists an $a_i$ such that $a_i > 0$. Thus, in any case, we will have $a_i < 0$ and $a_j > 0$ for some $i, j$. Thus, if $p$ is the number of $i \in \{0, 1, \dots, s-1\}$ such that $a_i > 0$, then $0 < p < s$. As a consequence,
$$s \mid \|a_0\|_* + \cdots + \|a_{s-1}\|_* = a_0 + a_1 + \cdots + a_{s-1} - p = -p,$$
which is a contradiction. Thus we must have $f(x) \in \{x, x+1\}$ for all $x \in \mathbb{N}$.