Let $\|x\|_*=(|x|+|x-1|-1)/2$. Find all $f:\mathbb{N}\to\mathbb{N}$ such that 
\[f^{(\|f(x)-x\|_*)}(x)=x, \quad\forall x\in\mathbb{N}.\]
Here $f^{(0)}(x)=x$ and $f^{(n)}(x)=f(f^{(n-1)}(x))$ for all $n\in\mathbb{N}$.

[i]Proposed by usjl[/i]
1. **Understanding the norm $\|x\|_*$:**
   \[
   \|x\|_* = \frac{|x| + |x-1| - 1}{2}
   \]
   We need to analyze this expression for different values of \(x\):
   - If \(x \geq 1\):
     \[
     |x| = x \quad \text{and} \quad |x-1| = x-1
     \]
     Thus,
     \[
     \|x\|_* = \frac{x + (x-1) - 1}{2} = \frac{2x - 2}{2} = x - 1
     \]
   - If \(0 \leq x < 1\):
     \[
     |x| = x \quad \text{and} \quad |x-1| = 1 - x
     \]
     Thus,
     \[
     \|x\|_* = \frac{x + (1 - x) - 1}{2} = \frac{0}{2} = 0
     \]
   - If \(x < 0\):
     \[
     |x| = -x \quad \text{and} \quad |x-1| = 1 - x
     \]
     Thus,
     \[
     \|x\|_* = \frac{-x + (1 - x) - 1}{2} = \frac{-2x}{2} = -x
     \]

2. **Analyzing the functional equation:**
   We need to find all functions \(f: \mathbb{N} \to \mathbb{N}\) such that:
   \[
   f^{(\|f(x) - x\|_*)}(x) = x \quad \forall x \in \mathbb{N}
   \]
   Here, \(f^{(n)}(x)\) denotes the \(n\)-th iterate of \(f\).

3. **Case analysis based on \(\|f(x) - x\|_*\):**
   - If \(\|f(x) - x\|_* = 0\):
     \[
     \|f(x) - x\|_* = 0 \implies f(x) - x = 0 \text{ or } f(x) - x = 1
     \]
     Thus, \(f(x) = x\) or \(f(x) = x + 1\).

   - If \(\|f(x) - x\|_* = 1\):
     \[
     \|f(x) - x\|_* = 1 \implies f(x) - x = 1
     \]
     Thus, \(f(x) = x + 1\).

4. **Uniqueness proof:**
   Suppose there exists \(x\) such that \(\|f(x) - x\|_* > 1\). Let \(t\) be the minimum integer such that \(f^{(t)}(x) = x\). For \(k = 0, 1, \ldots, t-1\), we have:
   \[
   t \mid \|f^{(k+1)}(x) - f^{(k)}(x)\|_*
   \]
   Notice that:
   \[
   \|x\| = \begin{cases} 
   x-1 & \text{if } x \ge 1 \\
   -x & \text{if } x \le 0 
   \end{cases}
   \]
   We have:
   \[
   t \mid f^{(k+1)}(x) - f^{(k)}(x) + \varepsilon_k \quad \text{for } k = 0, 1, \ldots, t-1
   \]
   where:
   \[
   \varepsilon_k = \begin{cases} 
   0 & \text{if } f^{(k+1)}(x) \le f^{(k)}(x) \\
   -1 & \text{if } f^{(k+1)}(x) > f^{(k)}(x) 
   \end{cases}
   \]
   Summing up, we get:
   \[
   t \mid \sum_{k=0}^{t-1} \varepsilon_k
   \]
   Since \(0 \ge \sum_{k=0}^{t-1} \varepsilon_k \ge -t\), we have \(\sum_{k=0}^{t-1} \varepsilon_k = 0\) or \(\sum_{k=0}^{t-1} \varepsilon_k = -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.

5. **Conclusion:**
   If \(\|f(x) - x\|_* = 1\), then \(f(x) = x\). Otherwise, \(\|f(x) - x\|_* = 0\), which implies \(f(x) - x = 0\) or \(f(x) - x = 1\). Therefore, \(f(x) = x\) or \(f(x) = x + 1\).

The final answer is \( \boxed{ f(x) \in \{x, x+1\} \ \ \forall x \in \mathbb{N} } \).