Wow this one is fire. Claim 1: $f(n)>n$. Obviously, $f(n)$ can't be $n$, else $k=1$ and $k=2$ works. Assume $f(n)<n$. Then $k=1$ works as $f(n)\le n+2$. Suppose $T$ is the unique number such that $f^T(f(n))\le f(n)+T+1$. Then $f^{T+1}(n)\le f(n)+T+1<n+T+2$, hence $k=T+1$ works for $n$ too! Now $k=1$ and $k=T+1$ both work for $n$, a contradiction to uniqueness. Claim 2: For every $n$, the unique $k$ is $1$. Suppose there is some $n$ such that the unique $k$ is not $1$. Then we must have $f^k(n)\le n+k+1$ but also $f^{k-1}(n)\ge n+k+1$. Thus, $f^{k-1}(n)$ fails claim 1, a contradiction. Claim 3: $f(n)=n+2$. From claim 2, we have both ($k=1$) $f(n)\le n+2$ and ($k=2$) $f(f(n))\ge n+4$. Thus $f(f(n))\ge n+4\ge f(n)+2\ge f(f(n))$, which means equality holds. Thus, $f(n)=n+2$ which can be easily checked to work.

Claim: $f(n) > n + 1$. Proof: Suppose $f(n) \le n + 1$ for some $n$. Then let $m$ be the $k$ for $f(n)$. We have \[f^{m+1}(n) \le f(n) +m + 1 \le n + (m+1) + 1,\]so $k=m + 1$ is valid for $n$. However, $f(n) \le n + 1 < n + 2$, so $k = 1$ is also valid, absurd. $\square$ Now if $k > 1$ for some $n$ is valid, then $f^{k-1}(n) < f^k(n) - 1 = n + (k-1) + 1$, so $k-1$ is also valid for $n$, contradiction. Therefore $k = 1$ is valid for all $n$, so $f(n) \le n + 2$, which combined with the first claim gives $\boxed{f(n) =n + 2}$, which works.

For every $n$ let $g(n)$ be the unique positive integer $k$ such that $f^k(n)\leq n+k+1$ Then $f^{g(f^{g(n)}(n))}(f^{g(n)}(n))\leq f^{g(n)}(n)+g(f^{g(n)}(n))+1\Leftrightarrow f^{g(f^{g(n)}(n))+g(n)}(n)\leq f^{g(n)}(n)+g(f^{g(n)}(n))+1\ $ Since $g(f^{g(n)}(n))+g(n)\neq g(n)$ we have that $f^{g(f^{g(n)}(n))+g(n)}(n)\geq g(f^{g(n)}(n))+g(n)+n+2$ so $g(f^{g(n)}(n))+g(n)+n+2\leq f^{g(n)}(n)+g(f^{g(n)}(n))+1\Leftrightarrow g(n)+n+1\leq f^{g(n)}(n) $ and thus $f^{g(n)}(n)=n+g(n)+1$. This means that in fact $f^k(n)\geq n+k+1$ for all positive integes $n,k$, therefore $f(n)\geq n+2$. Now $n+g(n)+1=f^{g(n)}(n)\geq n+2g(n)\Rightarrow g(n)=1$, so $f(n)=n+2$ for all $n$, which works.

Nice P1. We can see that $f(n) > n$, since if $f(n) \leq n$, $k+1$ must also satisfy the relation. If $k \geq 2$ for some $n$, $f^{k-1}(n) \geq n+k+1$ and $f^k(n) > f^{k-1}(n)$, creating a contradiction as $n+k+2 \leq f^k(n) \leq n+k+1$. Thus, $f(n) = n+1$ or $n+2$ If $f(n) = n+1$, $f(f(n)) \geq n+4$ but $f(f(n)) \leq f(n) + 2 = n+3$, causing a contradiction $\therefore f(n) = n+2$

We uploaded our solution https://calimath.org/pdf/IMOC2023-A1.pdf on youtube https://youtu.be/l8HParMvTy4.

The answer is $\boxed{f(n)=n+2\text{ for all } n\in\mathbb{N}}$. This works, because for all naturals $n$ and $m$, $f^m(n)=n+2m\geq n+m+1$, with equality if and only if $m=1$. We will prove that no other function satisfies. For a natural $n$, let $k_n$ be the unique integer satisfying the condition. Claim 1. $f(n)\geq n+2 \quad \forall n\in\mathbb{N}$

Proof. Reveal

Claim 2. $f(n)\leq n+2 \quad \forall n\in\mathbb{N}$

Proof. Reveal

Now combining both claims easily completes our solution.