Its easy to see that $ f(x) = x or x+1 \forall x$ works since that weird symbol evaluates to 0. If f(x) = x+2 or x-1, plug it in, we get x+2 = x and x-1 = x respectively, which does not work. For other cases, consider the sequence of s numbers :$a_1 = x, a_{i+1} = a_i$ , and $f(a_s) = x$, put them on a circle and add arrow to consecutive terms so it becomes a loop, color the arrows blue if $a_{i+1} $is greater than a_i, and red otherwise. Also assign a value for each arrow, indicating the difference between $a_{i+1}$ and $a_i$. For blue arrows, we have s|( $a_{i+1} - a_i$ - 1) For red arrows, we have s | ($a_{i+1} - a_i$) But the sum of red arrows is congruent to 0 mod s, So we have either 0 or s blue arrows, which simply doesnt work.

Let $\|x\|_*=g(x)$ For some $x$, let $p$ be the smallest natural number such that $f^p(x)=x$(if such a number exists). Now, we have $p|g(f(x)-x)$, thus $f(x)-x\in \{-kp, kp+1 \}$ for some whole number $k$. But, observe that this means that $f(x)-x\in \{0,1\}\pmod{p}$ but $f^p(x)-x=0\pmod{p}$, thus all of $f^{i+1}(x)-f^i(x)$ are $0$ or $1$. In case every is $1\pmod{p}$, we have that $f^{i+1}(x)>f^i(x)$ for all $i$ but we have $f^p(x)=x$, thus this is impossible. Now, if in every case it is $0\pmod{p}$, $f$ is non increasing but then it must always stay constant, and we get $p=1$. Thus, $f(x)=x$. Now, if such a $p$ doesn't exist then we cannot have $g(f(x)-x)>0\implies f(x)-x\in \{0,1\}$. But we have $f(x)\ne x$, so we get $f(x)=x+1$. Thus, $f(x)\in \{x,x+1\}$. We can now just arbitrarily set these values for all $x$ and all such functions work.

Nothing will be more funny than the first FE Taiwanese contestants waited for 8 tests looks so ugly and weird , which not even an algebra. Ans. $f(x) \in \{x, x+1\} \ \ \forall x \in \mathbb{N}$ Since in this case $\| f(x) - x\|_* = 0$, the equation definitely holds. Now we prove the uniqueness. If there exist $x$ such that $\| f(x) - x\|_* > 1$. Let $t$ be the minimum integer such that $f^{(t)}(x) = x$ ($t$ must exists). So for $k=0, 1, \cdots t-1$, we have $$ t \ |\ \|f^{(k+1)}(x) - f^{(k)}(x)\|_*$$Notice that $$\| x \| = \begin{cases} x-1 &, x \ge 1\\ -x &, x \le 0 \end{cases}$$We have $$ t \ | \ f^{(k+1)}(x) - f^{(k)}(x) + \varepsilon_k \ \ , k = 0, 1, \cdots t-1$$Where $$\varepsilon_k = \begin{cases} 0 &, f^{(k+1)}(x) \le f^{(k)}(x) \\ -1 &, f^{(k+1)}(x) > f^{(k)}(x) \end{cases}$$Sum it up we get $t \ | \ \sum_{k=0}^{t-1} \varepsilon_k$, and since $ 0 \ge \sum_{k=0}^{t-1} \varepsilon_k \ge -t$, we have $ \sum_{k=0}^{t-1} \varepsilon_k = 0, -t$. If $\sum_{k=0}^{t-1} \varepsilon_k = 0$, then $f^{(0)}(x) \ge f^{(1)}(x) \ge \cdots \ge f^{(t)}(x) $, which implies $f(x) = x$, contradiction. If $\sum_{k=0}^{t-1} \varepsilon_k = -t$ , then $ f^{(0)}(x) < f^{(1)}(x) < \cdots < f^{(t)}(x) $, also contradiction. Hence the initial assumption is false. If $ \| f(x) - x\|_* = 1$, then $f(x) = x$. Else $\| f(x) - x\|_* = 0$, which implies $f(x)-x = 0, 1$. We complete the proof. $\blacksquare$

Is there any way to solve it , if we have found that $f$ is injective ??

For any $n\in \mathbb N$ define $O(n) = \{n,f(n),f(f(n)),\cdots\}.$ Note that if there exists an integer $a\geq 1$ such that $f^a(n)=n$ then $O(n)$ is finite and $|O(n)|\; \bigg| \;a$. This fact is our main tool for solving the problem The answer is the functions $f$ such that for all $n$ we have $f(n) \in \{n,n+1\}$. In other words we will prove that $\|f(n)-n\|_*=0$ for all $n$. If $\|f(n)-n\|_*=1$ then $f(n)=n$ which gives that $\|f(n)-n\|_*=0$, a contradiction. Assume that there exists $n$ such that $s=\|f(n)-n\|_* >1$ . Then $O(n)$ is finite with cardinal $o_n$. In addition, we have $$O(n)= O(f(n)) = \cdots = O(f^{s-1}(n)),\;\; \text{and}\;\; o_n | s.$$Using the assertion for $f(n),f(f(n)),\cdots, f^{s-1}(n)$ we conclude that $o_n | \|f^{i+1}(n)-f^{i}(n)\|_*$ for all indices $i=0,1,2,\cdots, o_n-1$. For simplicity we write $a_ i : = f^i(n)$. We have $$o_n\bigg | \|a_{i+1}-a_i\|_* \leftrightarrow \begin{cases} a_{i+1}-a_i \equiv 0 \;\; (\text{mod} \; s)\;\;\; \text{when }\; a_{i+1}-a_i >0, \\ a_{i+1}-a_i \equiv 1 \;\; (\text{mod} \; s)\;\;\; \text{when }\; a_{i+1}-a_i<0. \end{cases}$$ Then we have $$ 0 \equiv (a_1-a_0)+ (a_2-a_1)+\cdots + (a_{o_n} - a_{o_n-1}) + (a_0 - a_{o_n}) \equiv \epsilon_1 + \epsilon_2+ \cdots + \epsilon_{o_n} \;\; (\text{mod}\; o_n )$$where $\epsilon_i \in \{0,1\}$. But this is false because at least one of the $\epsilon_i$'s in equal to $0$ and at least one of them is equal to $1$, because among $a_{i+1}-a_i$'s at least one of them is positive and at least one of them is negative and non of them is zero. So $o_n$ must be $0$ and this finishes the proof.