Beautiful problem! This is now one of my most favorite problems. The answer is $\boxed{\text{all } k \ge 2}$. Let $P(n)$ denote the assertion of $f^{g(n)}(n) = f(n) + k$. First, we'll set up a few lemmas. $\textbf{Sublemma 01.}$ There exists $m_0$ such that $f(m) = f(n) + ak$ for any $n,a \in \mathbb{N}$. $\textit{Proof.}$ To prove this, we'll use induction. Notice that there exists an integer $m_1$ such that $f(m_1) = f(n) + k$. Consider $P(m_1)$, we then have $m_2$ such that $f(m_2) = f(m_1) + k = f(n) + 2k$, continue doing this by induction, we then get our desired result. $\textbf{Sublemma 02.}$ For any integer $\ell, m$, we have $f^{\ell}(f(n) + mk) = f^{\ell + 1}(n) + mk$. $\textit{Proof.}$ We'll prove this by induction. By standard trick, \[ f(f(n) + k) = f(f^{g(n)}(n)) = f^{g(n)}(f(n)) = f(f(n)) + k \]Therefore, we can get that if $f^{\ell} (f(n)+k) = f^{\ell + 1}(n) + k$, then $f^{\ell + 1}(f(n) + k) = f^{\ell}(f(f(n)) + k) = f^{\ell + 1}(f(n)) + k = f^{\ell + 2}(n) + k$. Now consider $m_{a - 1}$ such that $f(m_{a - 1}) = f(n) + (a - 1)k = f(m_{a - 2}) + k$ which exists by Sublemma 01, then \[ f^{\ell} (m_a) = f^{\ell - 1}(f(m_{a - 1}) + k) = f^{\ell}(m_{a - 1}) + k \Rightarrow f^{\ell}(f(n) + ak) = f^{\ell + 1}(n) + ak\] Now, we'll prove the following main claim. $\textbf{Claim 01.}$ There doesn't exists any value of $\ell > 0$ such that $f^{\ell} (n) = n$ for any $n \in \mathbb{N}$. $\textit{Proof.}$ Define $\mathcal{A}$ as the set of values of $f^{k}(n)$, where $k \in \mathbb{N}$. To prove this, we'll prove that $f^a(n) + ak \in \mathcal{A}$ for any $a \in \mathbb{N}$. We'll prove this by induction. For $n = 1$, this is obvious. Then, plug $P(f^{g(n)}(n))$ and we have \[ f^{g(f(n) + k) + g(n)}(n) = f(f(n)) + 2k \]Now, suppose $f^{a}(n) + ak \in \mathcal{A}$, then we have $f^{X_{n,a}}(n) = f^a(n) + ak$ for some $n,a$ and $X_{n,a}$ is a variable depending on $n$ and $a$. Then, replace all $n$ with $f^{g(n)}(n) = f(n) + k$, we get \[ f^{X_{f(n) + k,a} + g(n)}(n) = f^a(f(n) + k) + ak = f^{a + 1}(n) + (a + 1)k\]Therefore, we are done by induction. Now notice that the sequence $\{f^i(k) + ik\}_{i = 1}^{\infty}$ is unbounded. Since they are all members of $\mathcal{A}$, then $|\mathcal{A}| = +\infty$. However, if there exists $\ell$ such that $f^{\ell}(n) = n$, then $|\mathcal{A}|$ is finite, a contradiction. Now, to finish this problem off. Notice that $P(f(n) + ak)$ gives us \[ f^{g(f(n) + ak)}(f(n) + ak) = f(f(n) + ak) + k \]By our lemma, $f^{g(f(n) + ak) + 1}(n) + ak = LHS = RHS = f(f(n)) + (a + 1)k$ , which therefore gives us \[ f^{g(f(n) + ak) + 1}(n) = f(f(n)) + k \]for any $a \in \mathbb{N}$. However, this gives us \[ f^{g(f(n) + ak) + 1}(n) = f(f(n)) + k = f(f(n) + k) = f(f^{g(n)}(n)) = f^{g(n) + 1}(n) \]Therefore, we have \[ f^{|g(f(n) + ak) - g(n)|}(n) = n \]for all $n \in \mathbb{N}$. Therefore, we have $g(n) = g(f(n) + ak)$ for all $a \in \mathbb{N}$. For $k = 1$, there are no such functions obviously as this contradicts $g$ is unbounded. Construction for $k \ge 2$: Consider $f(k^n) = nk + 1$ and $f(nk + 1) = k^n + 2$. For any $a$, which is not a power of $k$, we can let $f(ak) = ak + 2$ and define $f(x) = x + 1$ for any other integers $x$ not mentioned. One can define $g(n)$ to be the smallest $m$ satisfying $f^m(n) = f(n) + k$. One can check that $g$ is unbounded since $g(nk + 1)$ is the number of integers $m$ such that $k^n + 2 \le m \le k^{n + 1}$ and $k \nmid m - 1$.

Here's a different solution.

This problem is esentially graph theory. If we take $\mathbb N$ to be the vertices and pairs $(x, f(x))$ to be the edges of an infinite directed graph in which every vertex has outdegree exactly $1$, the condition implies that for every vertex $x$ with indegree at least $1$, there exists a path from $x$ to $x+k$. With this approach, it's easy to visualise everything and the fact that $k=1$ doesn't work is visually clear and fairly routine to prove (there are no cycles and this forces $f(x)$ to be directly connected to $f(x)+1$ ). For $k>1$, we can split the vertices in classes modulo $k$, pick a particular class (say $\{1,k+1,\ldots,\}$), and make paths from $ak+1$ to $(a+1)k+1$ arbitrarily long by connecting $ak+1$ to some number from another class and then moving along this other class for a while before coming back to $(a+1)k+1$.

Remark : Another beautiful arrow problem, but too hard for a P1 imho We claim that all $k>1$ works. First we show that $k=1$ doesn't work. First note that $f$ cannot have a cycle. Otherwise we could consider the maximal element $m$ of the cycle and get that $f^{g(m)}(m)=m+k>m$ also resides in the same cycle as that of $m$ , hence we arrive at a contradiction.

associate a positive integer $h(n)$ to it such that $f^{h(n)}(b)= b+n$. Also note that the map $h(n) \mapsto n$ is obviously injective. Hence the map $h : \mathbb N \mapsto \mathbb N$ is a bijection. We now claim that $h$ is monotone increasing. We will use that fact that $f^{n}(\bullet)$ is injective in $n$. We have : $$ f^{h(n+1)}(b)= (b+n)+1= f^{h(n)}(b)+1= f\left( \underbrace {f^{h(n)-1}(b)}_{x} \right)+1= f(x)+1=f^{g(x)}(x)= f^{g(x)+h(n)-1}(b)$$$$\implies h(n+1)= g(x)+h(n)-1>h(n)$$ Hence we must have $h(n)=n$. This gives $f^n(b)=b+n$. This rearranges to give $f^2(n)=f(n)+1$ which means $g(n)=2 (\rightarrow \leftarrow)$. Construction for $k>2$ is similar to the ones provided by the users above . $\blacksquare$. @below thanks for clarifying , I wasn't aware of that

Aryan-23 wrote: Remark : Another beautiful arrow problem, but too hard for a P1 imho MEMO problems are sorted by subject, not difficulty. In particular, Individual P1,2,3,4 are always A,C,G,N in that order.

Solved with nukelauncher. The answer is \(k\ge2\). In what follows, we draw arrows of the form \(n\to f(n)\). The condition is that for \(a\in f(\mathbb N)\), there are arbitrarily long chains from \(a\) to \(a+k\). \bigskip Construction for \(k\ge2\): The core idea is to bounce between residue classes modulo \(k\): if \(a_{ij}=i+k(j-1)\), take \begin{align*} &a_{11}\to a_{21}\to a_{31}\to\cdots\to a_{k1}\\ \to&\;a_{12}\to a_{22}\to a_{32}\to\cdots\to a_{k2}\to a_{k3}\\ \to&\;a_{13}\to a_{23}\to a_{33}\to\cdots\to a_{k4}\to a_{k5}\to a_{k6}\\ \to&\;\cdots \end{align*} \bigskip Impossibility for \(k=1\): First observe that there are no cycles: if there is a cycle, consider the largest number \(m\) in the cycle. Then there is no chain from \(m\) to \(m+1\), contradiction. Now note that \(f(n)>n\) for all \(n\); if \(f(n)\le n\), then we have a cycle of the form \[n\to f(n)\to\cdots\to f(n)+1\to\cdots\to f(n)+2\to\cdots\to\cdots\to n.\] Finally, we must have \(f(n)\equiv n+1\). If \(f(n)\ge n+2\), then there is no chain from \(n\) to \(n+1\), contradiction. But then \(g\equiv1\), so \(k=1\) fails.

dame dame