A new addition to what I consider my favorite problems. Elegant statement, very fun to work on, and a nice solution. Unfortunately since I had to present the problem at the US training camp for a test review I was unable to finish it before having to look up a solution (major bummer there). I had to work everything out again since that was awhile ago, but I think this solution still resembles the second official solution pretty closely. Step 1: $f(m) = f(n) \Leftrightarrow g(m) = g(n)$. If $f(m) = f(n)$, then $g(m) = g(f(m)) - 1 = g(f(n)) - 1 = g(n)$ from the second equation. The exact same argument shows the converse. Step 2: $f(f(m)) = f(f(n)) \Rightarrow f(m) = f(n)$, and a similar fact holds for $g$. If $f(f(m)) = f(f(n))$, then by step 1 applied to $f(m), f(n)$, we get $g(f(m)) = g(f(n))$, or $g(m)+1 = g(n)+1$. By step 1 again this implies $f(m) = f(n)$. Step 3: $f(n) \neq n$ and $g(n) \neq n$ for all $n$. If $f(n) = n$, then putting that into the second equation gives $0 = 1$, a contradiction. Use the first equation to prove the same thing for $g$. Step 4: There exist $a,b$ such that $\text{Im}\ f = \{a, a+1, \ldots \}$ and similarly $\text{Im}\ g = \{b, b+1, \ldots \}$. Notice that if $f(x) = y$ for any $x,y$, then $n = x$ in the first equation gives that $y+1$ is in the range of $f$. Hence $y$ being in the range implies $y+1$ is; the existence of $a$ follows immediately. The exact same argument on the second equation gives the same thing for $g$. Step 5: With the same $a,b$ as in step 4, $f(a) \geq a+1$ and $g(b) \geq b+1$. Step 4 gives $f(a) \geq a$ and $g(b) \geq b$. Step 3 gives $f(a) \neq a$ and $g(b) \neq b$. The conclusion follows. Step 6: $a = b$. Without loss of generality, $a \geq b$. Because $g(b) \geq b+1$ from step 5, $g(b) - 1$ is in the range of $g$. Hence there exists a $c$ with $g(c)+1 = g(b)$. Plug $n = c$ into the second equation to get $g(f(c)) = g(b)$. Because $f(c) \geq a \geq b$ and all numbers at least $b$ are in the range of $g$, step 2 allows us to cancel the $g$'s and conclude that $f(c) = b$. This implies $b \geq a$, and since we assumed WLOG earlier that $a \geq b$ we have $a = b$ as desired. Step 7: $g(b) = b+1$, and similarly $f(a) = a+1$. Suppose $g(b) \neq b+1$. Combined with step 5 we can say $g(b) \geq b+2$. Then $g(b) - 2$ is in the range of $g$, so there exists a $c$ with $g(c) + 2 = g(b)$. Notice that $g(f(f(c))) = g(f(c)) + 1 = g(c) + 2 = g(b)$. The same trick with step 2 allows us to cancel the $g$'s and conclude $f(f(c)) = b$. Since $f$ and $g$ have the same range by step 6, we can find a $d$ with $f(c) = g(d)$. Then $b = f(g(d)) = f(d) + 1 \geq b+1$, a contradiction. Proving $f(a) = a+1$ is exactly the same. Step 8: $f(x) = g(x) = x+1$ for $x \geq a$. By induction, with the base case $x = a$ already proven in step 7. Given it's true for $x$, plug $n = x$ into the first equation to get $f(g(x)) = f(x)+1$, or $f(x+1) = x+2$. Use the second equation similarly to get $g(x+1) = x+2$, completing the induction. Step 9: $f(n) = g(n)$ for all $n$. From the first equation we have $f(g(n)) = f(n)+1$. Because $g(n) \geq a$, step 8 allows us to say that $f(g(n)) = g(n)+1$. Thus $f(n) = g(n)$ as wanted.

Hmm, hopefully this is correct...

Hmm, I feel like pretty much any solution to the simpler problem "$h^2(n) = h(n)+1$ for all $n\ge1$" can be adapted to this version. Anyway, here's a method that doesn't explicitly use $f^2(a) = f^2(b)\implies f(a) = f(b)$, although it certainly can be reworded in terms of things like $f\circ g\circ f$. Let $L_n = \{n,n+1,n+2,\ldots,\}$ for $n\ge1$, and define $h(A) = \{h(a):a\in A\}$ for any set $A$ and function $h$. As shown above, there clearly exist positive integers $r,s$ such that $f(L_1) = L_r$ and $g(L_1) = L_s$. Then \[ f(L_s) = f(g(L_1)) = f(L_1) + 1 = L_r + 1 = L_{r+1} \]and similarly, $g(L_r) = L_{s+1}$. In the same manner, we obtain \[ f(L_{s+1}) = f(g(L_r)) = f(L_r) + 1\not\supseteq f(L_r), \]whence $s+1>r$; similarly, $r+1>s$, so $r=s$. Now $f(L_r) = f(L_s) = L_{r+1}$ and $f(L_{r+1}) = f(L_{s+1}) = f(L_r) + 1 = L_{r+1} + 1 = L_{r+2}$, so we must have $f(r) = r+1$ (or else $f(L_r) = \{f(r)\}\cup f(L_{r+1}) = L_{r+2}$). The rest is not hard: we can show $f(n) = g(n) = n+1$ for $n\ge r$ by induction, and for $m<r$, note that $g(m)+1 = f(g(m)) = f(m)+1$ (since $f(m)\ge r$).

I believe this to be a pretty problem. Obviously $f(x)=f(y) \Leftrightarrow g(x)=g(y)$, $f(x) \neq x \neq g(x)$, and the image of $f$ is the set of numbers $\ge F$ for some $F$ and the image of $g$ is the set of numbers $\ge G$ for some $G$. Notice $f(f(a))=f(f(b)) \Rightarrow g(a)+1=g(f(a))=g(f(b))=g(b)+1 \Rightarrow g(a) = g(b) \Rightarrow f(a)=f(b)$ and so $f(x)=f(y)$ implies one of them is $<F$ (or $x=y$). So $f$ is "inyective" in $\mathbb{N}_{\ge F}$ and $g$ is "inyective" in $\mathbb{N}_{\ge G}$. Now assume $G<F$ we achieve $g(G) \ge G+1 \Rightarrow g(G) = g(x)+1$ for some $x$, and so $g(G)=g(f(x))$ but $f(x) \ge F > G$ and by injectivity, $G=f(x) \ge F>G$, contradiction. Also $F<G$ is impossible and so $F=G$. Now notice that if $g(x)=G$ for some $x \ge G$ then $x=f(y)$ for some $y$ and therefore $G=g(x)=g(f(y))=g(y)+1$ impossible. Also notice that if we have $A \ge G+1$ then $A-1=g(x)$ for some $x$ and so $g(f(x))=A$ and $f(x) \ge G$. Therefore $g$ is a bijection $g(\mathbb{N}_{\ge G}) \mapsto \mathbb{N}_{\ge G+1}$ and similarly so is $f$. Now if $g(G+k)=G+1$ for some $k \ge 1$ then $G+k=f(x)$ for some $x \ge G$ and so $G+1=g(G+k)=g(f(x))=g(x)+1 \Rightarrow g(x)=G$ contradiction. But by bijectivity this implies $g(G)=G+1$ and similarly for $f$. Therefore $g$ is a bijection $g(\mathbb{N}_{\ge G+1}) \mapsto \mathbb{N}_{\ge G+2}$ and so is $f$. By induction we achieve $g(x)=f(x)=x+1$ for all $x \ge G$. Now the problem condition now states that since $g(n) \ge G$ always then $f(g(n))=g(n)+1$ and so $f(n)+1=g(n)+1$ for all $n$ and so $\boxed{f=g}$. Done.

Let $P(n)$ and $Q(n)$ denote the two given assertions, respectively. Claim: [Contiguous images] The images of $f$ and $g$ are of the form \begin{align*} f({\mathbb N}) &= \left\{ A, A+1, \dots \right\} \\ g({\mathbb N}) &= \left\{ B, B+1, \dots \right\} \end{align*}for some $A$ and $B$. Proof. If $f(n) \in f({\mathbb N})$, then $f(n)+1 = fg(n) \in f({\mathbb N})$, by $P(n)$. Similarly for $g$. $\blacksquare$ Let us assume WLOG that $A \le B$. The main lemma is the following (see IMO 1977/6 for a similar argument): Lemma: [Main estimate] We have $g(n) \ge f(n) + (B-A)$ for every $n \ge 1$. Proof. We prove the sentence \[ S(k) \colon \quad \text{If } n \ge A+k \text{ then } g(n) \ge B+k+1 \]by induction on $k$. For $k = 0$ this follows by varying $n$ in assertion $Q$. Now note that \begin{align*} g(n) &\ge B \\ \implies gg(n) &\ge B+1 &\text{by $S(0)$} \\ \implies ggg(n) &\ge B+2 &\text{by $S(1)$} \\ & \vdotswithin\ge \\ \implies g^{k}(n) &\ge B+(k-1) &\text{ by $S(k-2)$} \\ \implies g^{k+1}(n) &\ge B+k &\text{ by $S(k-1)$}. \end{align*}But \[ g(f(n)+k) = (g \circ f \circ g^k)(n) = g^{k+1}(n) + 1 \ge (B+k)+1. \]which implies $S(k)$. Now for any particular $m$, we have $g(m) \ge m+(B-A+1)$. Replacing $m$ with $f(n)$ gives $1 + g(n) = g(f(n)) \ge f(n) + (B-A+1)$ as needed. $\blacksquare$ Claim: [$f$ has no eventual cycles] For any $k > 0$ and $n \ge 1$, we have $f^k(n) \neq n$. Proof. Otherwise, $g(n) + k = (g \circ f^k)(n) = g(n) \implies k = 0$, contradiction. $\blacksquare$ Claim: [We found all functions!] For $n \ge A$, we have \[ f(n) = n+1 \qquad g(n) = n+(B-A+1). \] Proof. By induction on $n \ge A$. For the base step, pick $x_0$ such that $g(x_0) = B$. By the main lemma, we have $B = g(x_0) \ge f(x_0) + (B-A) \implies f(x_0) = A$. Hence, $Q(x_0) \implies g(A) = B+1$. Finally, \[ B+1 = g(A) \ge f(A) + (B-A) \implies f(A) \le A+1. \]Since $f(A) \neq A$, but also $f(A) \ge A$ from the range of $f$, it follows $f(A) = A+1$. The inductive step is almost the same: assume we know $f$ and $g$ up to $n-1$. Then \[ g(n) = g(f(n-1)) = g(n-1) + 1 = n + (B-A+1). \]Now by the main lemma, \[ n + (B-A+1) = g(n) \ge f(n) + (B-A) \implies f(n) \le n+1. \]But since $f$ has no eventual cycles, and we already have a chain \[ A \xmapsto{f} (A+1) \xmapsto{f} (A+2) \xmapsto{f} \dots \xmapsto{f} (n-1) \xmapsto{f} n \]we must have $f(n) = n+1$ since it can't map to any values in $\{A , \dots, n\}$. $\blacksquare$ Now $P(n)$ reads $f(n)+1 = f(g(n)) = g(n)+1$ since $g(n) \ge A$. Thus $f = g$. Remark: From here it easy to characterize all functions. We have $A=B$ and $f(n) = g(n) = n+1$ for all $n \ge A$. The values of $f(n) = g(n)$ may be arbitrary for $n < A$, as long as they are at least $A$.

A really elegant problem, but it took me a really long time to write up the details. Lemma 01. $f(a) = f(b) \Leftrightarrow g(a) = g(b)$. Proof. Notice that $f(a) = f(b)$ gives us \[ g(f(a)) = g(f(b)) \]\[ g(a) + 1 = g(b) + 1 \]Therefore, $g(a) = g(b)$. A similar method to show the other way around. Lemma 02. $f(f(a)) = f(f(b)) \Leftrightarrow f(a) = f(b)$, and $g(g(a)) = g(g(b)) \Leftrightarrow g(a) = g(b)$. Proof. Notice that by Lemma 01, since $f(f(a)) = f(f(b))$, we must have $g(f(a)) = g(f(b))$. This results to $g(a) = g(b)$. Applying Lemma 01 once more, we conclude that $f(a) = f(b)$. A similar method holds for $g(g(a)) = g(g(b)) \Leftrightarrow g(a) = g(b)$. Lemma 03. There exists $a,b \in \mathbb{N}$ such that $\text{Im}_f = \{ a, a + 1, a + 2, \dots \}$ and $\text{Im}_g = \{ b ,b + 1 , b + 2, \dots \}$. Proof. Notice that by Well Ordering Principle, there exists a minimal element in $\text{Im}_f$, call it as $a$, and notice that $f(g(f^{-1}(a))) = a + 1$, and by repeating the 2nd equation, we can have $a + k, k \in \mathbb{N}$, all in $\text{Im}_f$. The same method holds for $g$. Lemma 04. $f(a) \ge a + 1$ and $g(b) \ge b + 1$. Proof. Notice that by Lemma 03, $f(a) \ge a$ and $g(b) \ge b$. But we know that if $f(a) = a$, plug this in to the 2nd equation, we have $g(a) = g(f(a)) = g(a) + 1$, which is absurd. Therefore, we must have $f(a) \ge a + 1$. A similar method is used for $g$. Lemma 05. $a = b$. Proof. WLOG $a \ge b$. Since $g(b) \ge b + 1$ and $\min \text{Im}_g = b$. There exists a $c \in \mathbb{N}$ such that $g(c) + 1 = g(b)$. Now, notice that $g(f(c)) = g(c) + 1 = g(b)$. Moreover, $f(c) \ge a \ge b$, since $\min \text{Im}_f = a$. Therefore, we have $f(c)$ and $b$ are both image on $g$. Thus, by using Lemma 02, we know that $f(c) = b$. But we know that $b = f(c) \ge a$. Therefore, we conclude that $a = b$. Lemma 06. $f(a) = a + 1$ and $g(b) = b + 1$. Proof. Suppose otherwise, that $f(a) \ge a + 2$. Therefore there exists a constant $c$ such that $f(a) = f(c) + 2$. Now, notice that \[ f(a) = f(c) + 2 = f(g(c)) + 1 = f(g(g(c))) \]Therefore by Lemma 02 , we have $g(g(c)) = a$. Now, notice that $\text{Im}_f = \text{Im}_g$, so we can find a constant $d$ such that $g(c) = f(d)$. \[ a = g(g(c)) = g(f(d)) = g(d) + 1\]which gives us $g(d) = a - 1$, a contradiction as $\min \text{Im}_g = a$, a similar method holds for $g$. Now, notice that $f(g(a) + 1) = f(f(a)) + 1$ by plugging $n = f(a)$ to the first equation and apply the second equation. Since we have $f(a) = a + 1 = g(a)$. Then we must have $f(a + 1) = f(g(a)) = f(a) = g(a) = g(f(a)) = g(a + 1)$, and one could prove by induction that $f(n) = g(n)$ for all $n \ge a$. Now, we will consider the case where $n < a$. Since $\min \text{Im}_f = \min \text{Im}_g = a$. Then we must have a constant $m$ such that $f(n) = f(m)$, where $m > a$, as the set $f(n)_{n \ge a}$ contains all the numbers from $a$ and above. By Lemma 01, since $f(n) = f(m)$, we must have $g(m) = g(n)$ as well. But, \[ f(n) = f(m) = g(m) = g(n) \]Therefore, the statement is true for all $n \in \mathbb{N}$.

First, we prove the following. Claim: We have $f(\mathbb{Z}^+) = \{A,A+1,A+2,\hdots\}$ for some $A$. Similarly, $g(\mathbb{Z}^+) = \{B,B+1,B+2,\hdots,\}$ for some $B$. Proof: Take the smallest element, say $A$ in $F = f(\mathbb{Z}^+)$. Since $f(g(n)) = f(n)+1$ we get $x\in F$ $\implies x+1\in F$, therefore $A+1\in F$, $A+2\in F$,... The result follows. $\blacksquare$ Assume that $A\leq B$. Take $x$ such that $f(x)=A$ and consider the chain of $g$. We have the following facts. $f(g^n(x)) = f(g^{n-1}(x))+1 = \hdots = f(x)+n$. $g(A+n) = g(f(g^n(x))) = g^{n+1}(x)+1$. Putting in picture, we have the following. $$\begin{array}{ccccccc} x & \stackrel{g}{\rightarrow} & g(x) & \stackrel{g}{\to} & g^2(x) & \stackrel{g}{\to} & \hdots \\[4pt] \ \downarrow^f & & \ \downarrow^f & & \ \downarrow^f & \\[4pt] A & & A+1 & & A+2 & & \hdots \\[4pt] \ \downarrow^g & & \ \downarrow^g & & \ \downarrow^g & \\[4pt] g(x)+1 & & g^2(x)+1 & & g^3(x)+1 & & \hdots \end{array}$$Now we exclude the following trivial case. Claim: If $g(x)=A$, we are done. Proof: Note that this implies $A=B$. We first induct on $k$ that $g(A+k) = A+k+1$ for any $k\geq 0$. For the base case, note that $g(A) = g(f(x)) = g(x)+1 = A+1$. For the inductive step, note that $g^k(A) = g^{k-1}(A+1) = g^{k-2}(A+2) =\hdots = A+k$. $g(A+k) = g^{k+1}(x)+1 = g^k(A)+1 = A+k+1$. hence the claim is true for $k+1$, hence proven. Since $f(x)\geq A$ for all $x$, this gives $g(x)+1 = g(f(x)) = f(x)+1$ for all $x$ hence we are done.$\blacksquare$. Assume that $g(x)>A$. Since $g^k(x)\geq B\geq A$, we have $g^{k+1}(x) $ $= g(A+[g^k(x)-A+1])$ $= g^{g^k(x)-A}(x)+1$ which means. $$\boxed{g^{g^k(x)-A}(x)+1 = g^{k+1}(x)} \qquad (*)$$for any $k\in\mathbb{Z}^+$. In fact, we can extract most informations about $g$ from $(*)$. First, we proceed similarly to IMO 1977 P6. Claim: $g^k(x)$ is the unique smallest element in $G_k = \{g^k(x), g^{k+1}(x), g^{k+2}(x),\hdots\}$. Proof: Induct on $k$. The base case and the inductive step are the same so we will do them together. Suppose that $g^t(x)$ is the maximum element of $G_k$ where $t>k$. Then by induction hypothesis (if $k>1$), $$g^{\ell}(x) > g^{k-1}(x) > g^{k-2}(x) > \hdots > g(x)\geq A+1$$which means $g^{\ell}(x)\geq B+k\geq A+k$ for any $\ell\geq k$. Since $t-1\geq k$, we get $$g^{g^{t-1}(x)-A+1}(x)+1 = g^t(x)$$but $g^{t-1}(x)-A+1\geq k$, which gives the contradiction. $\blacksquare$ The claim implies $g(x) < g(g(x)) < \hdots $. Thus using $(*)$ again, we deduce $$g^k(x)-A+1 < k+1 \implies g^k(x)\leq A+k-1$$for any $k\in\mathbb{Z}^+$. This focres $g(x)=A$ so we are done.

First note that from the first equation, $k\in Im(f)$ implies $k+1\in Im(f)$, meaning that $Im(f)=\mathbb{N}_{\ge a}$ for some $a$, and similarly $Im(g)=\mathbb{N}_{\ge b}$ for some $b$. It is also easy to see that $f(m)=f(n)\iff g(m)=g(n)$, so $f(f(m))=f(f(n))\iff g(f(m))=g(f(n))\iff g(m)=g(n)\iff f(m)=f(n)$. Therefore, $f(f(m))=f(f(n))\iff f(m)=f(n)$, meaning that $f$ is injective in $\mathbb{N}_{\ge a}$, and similarly $g$ is injective in $\mathbb{N}_{\ge b}$. We'll now prove $a=b$; first WLOG $a\ge b$, and it is also clear that $f, g$ do not have any fixed points, so $f(a)\ge a+1$ and $g(b)\ge b+1$. This means $g(b)-1\ge b$ so $g(b)-1=g(c)$ for some $c$; then, $g(b)=g(c)+1$, so $g(f(c))=g(c)+1=g(b)$. Since $g$ is injective in $\mathbb{N}_{\ge b}$ and $f(c)\ge a\ge b$, we have $f(c)=b$, so thus $a=b$. Thus, $Im(f)=Im(g)=\mathbb{N}_{\ge a}$. Now I'll prove $f(a)=a+1$; suppose otherwise FTSOC that $f(a)\ge a+1$, so then $f(a)-2=f(k)$ for some $k$. Now note that we have $f(g(g(k)))=f(g(k))+1=f(k)+2=f(a)$, meaning that $g(g(k))=a$ by injectivity. But note that since $g(k)\ge a$, there exists $j$ such that $f(j)=g(k)$. Thus, $a=g(f(j))=g(j)+1$, which is a contradiction by minimality of $a$. Hence, we have that $f(a)=a+1$, and similarly $g(a)=a+1$; now, suppose that $f(x)=g(x)=x+1$, then $f(g(x))=f(x)+1$ meaning that $f(x+1)=x+2$ and similarly $g(x+1)=x+2$. Hence, by induction we have that $f(x)=x+1$ for all $x\ge a$. Finally, note that since $g(n)\ge a$, for all $n$ we have $g(n)+1=f(n)+1$, meaning $f(n)=g(n)$ for all $n$, as desired.

EDIT: 250 POSTS !!!! yay!!!

Solved with eisirrational and goodbear. First note the following identities: For each $n$, we have $f(n)\ne n$; else $g(n)=g(f(n))=g(n)+1$. (Similarly $g(n)\ne n$.) $f(a)=f(b)\implies g(f(a))=g(f(b))\implies g(a)=g(b)$, i.e.\ $f(a)=f(b)\iff g(a)=g(b)$. $f(f(a))=f(f(b))\iff g(f(a))=g(f(b))\iff f(a)=f(b)$. In particular, if $f(a)=f(b)$ and $a,b\in f_*(\mathbb N)$, then $a=b$. Henceforth we will refer to this property as pseudo-injectivity. The key is to describe the ranges of $f$, $g$, which we will do in the following two claims. Claim: For some $j$, $k$, we have $f_*(\mathbb N)=\{j,j+1,\ldots\}$ and $g_*(\mathbb N)=\{k,k+1,\ldots\}$. Proof. Note that if $f(n)\in f_*(\mathbb N)$, then $f(n)+1=f(g(n))\in f_*(\mathbb N)$, and similarly $g(n)\in g_*(\mathbb N)$ implies $g(n)+1\in g_*(\mathbb N)$. $\blacksquare$ Claim: $f(j)=g(k)$. Proof. Assume without loss of generality $f(j)\le g(k)$. Since $f(f(j))\ne f(j)$, for some $\ell$ we have $f(f(j))=f(\ell)+1=f(g(\ell))$. But $g(\ell)\ge g(k)\ge f(j)$, so $g(\ell)\in f_*(\mathbb N)$. By pseudo-injectivity $f(j)=g(\ell)\ge g(k)$, thus $f(j)=g(k)$. $\blacksquare$ Henceforth we let $f(j)=g(k)=c$, so that $f_*(\mathbb N)=g_*(\mathbb N)=\{c,c+1,\ldots\}$. In the next two claims we prove $f(n)=g(n)$ for cofinitely many $n$: Claim: $f(c)=c+1$. Proof. Assume for contradiction $f(c)-2\ge c$. Then for some $\ell$, we have \[f(c)-2=f(\ell)=f(g(\ell))-1=f(g(g(\ell)))-2.\]Note $g(\ell)=f(\ell')$ for some $\ell'$. By pseudo-injectivity \[c=g(g(\ell))=g(f(\ell'))=g(\ell')+1,\]so $c-1\in g_*(\mathbb N)$, which is absurd. $\blacksquare$ Claim: $f(n)=g(n)=n+1$ for $n\ge c$. Proof. The proof is by induction on $n$, where the base case $n=c$ is the above claim. If $f(n-1)=g(n-1)=n$, then \[f(n)=f(g(n-1))=f(n-1)+1=n+1,\]and similarly $g(n)=n+1$, as claimed. $\blacksquare$ To finish, note that for each $n$, we have $f(f(n))=f(n)+1=f(g(n))$ by the above claim. By pseudo-injectivity, $f(n)=g(n)$, and we are done.

We'll go through the problem in steps.

$\blacksquare\blacksquare$

why revealed like that

Solution with GeronimoStilton. For fun, here is a nontrivial solution: \[f(n)=g(n)=\begin{cases} c&n<c\\ n+1&n\ge c \end{cases}\forall c\in\mathbb{N}.\]Observe that -- If $c$ is the minimal element of $g(\mathbb{N})$, then $c+1,c+2,\dots$ are all in $g(\mathbb{N})$ by the given. A similar result holds for the minimal element $d$ of $f(\mathbb{N})$. -- If $f(a)=f(b)$ then $g(a)=g(b)$ and vice versa. In all claims we note the claim with $f$ and $g$ swapped holds by symmetry. Claim 1.If $g(g(m))=g(g(n))$ then $g(m)=g(n)$. Proof. Apply $f$ to both sides. Claim 2. We have $c=d$. Proof. Suppose otherwise. WLOG, $c<d$. Then take some $g(x)=g(c)-1$ since $g(c) \neq c$ and therefore $g(c)\geq c+1$. Now, $g(f(x))=g(c)$ and since $f(x),c$ are both in the range of $g$ we can simplify to $f(x) = c < d$ by Claim 1, which is stupid and therefore $c=d$. This means that we no longer have to differentiate between $c$ and $d$. Claim 3. $f(c+t) = g(c+t) = c+t+1$ for $t\geq0$. Proof. For the base case: Assume for sake of contradiction that there exists $x$ such that $f(x)+2 = f(c)$. Then $$f(g(g(x))) = f(x)+2 = f(c)$$and since both $g(g(x))$ and $c$ are in the range of $f$ we can reduce: $$g(g(x)) = c$$but then $g(g(x)) = g(y) + 1 = c$ for some $y$ with $g(x) = f(y)$ and this is clearly ridiculous. Hence no such $x$ exists and $f(c)=c+1$; similarly $g(c)=c+1$. So then suppose $f^{t+1}(c)>c+t+1$ for contradiction which we can do by Claim 1 and the induction hypothesis. Then we can let $f^{t+1}(c)=f(x)+t+2=f(g^{t+2}(x))$ so $g^{t+2}(x)=f^t(c)=c+t$. So applying $g^{-1}$ a total of $t$ times yields $g(g(x))=c$, which is bad again. Claim 4. If $n<c$ then $f(n)=g(n)$. Proof. Note \[f(n)+1=f(g(n))=g(n)+1\]because $f$ is $t\mapsto t+1$ for $t\ge c$, and $g(n) \ge c$. Combining Claims 3 and 4, we are done.

orl wrote: Suppose that $f$ and $g$ are two functions defined on the set of positive integers and taking positive integer values. Suppose also that the equations $f(g(n)) = f(n) + 1$ and $g(f(n)) = g(n) + 1$ hold for all positive integers. Prove that $f(n) = g(n)$ for all positive integer $n.$ Proposed by Alex Schreiber, Germany Very nice problem. Let $P(x, y)$ be the assertion. We see that if $f(x) = f(y)$ for two positive integers $x, y$, then $g(x) +1 = g(f(x)) = g(f(y)) = g(y) + 1 \implies g(x) = g(y)$, and the converse also holds true similarly. If $f(f(x)) = f(f(y))$, then $g(f(x)) = g(f(y)) \implies f(x) + 1 = g(f(x)) = g(f(y)) = f(y) + 1 \implies f(x) = f(y)$ and similarly $g(g(x)) = g(g(y)) \implies g(x) = g(y)$. Also $f(x) \neq x, g(x) \neq x$ as these give straight contradiction. Observe that if $k \in \text{Img}(f)$, and if $f(x) = k$ for some $x \in \mathbb{Z}^+$, then $f(g(x)) = f(x)+1 = k+1 \implies \text{Img}(f) = \{ a, a+1, a+2 \dots \}$ for some $a \in \mathbb{Z}^+$ and similarly $\text{Img}(g) = \{ b, b+1, b+2 \dots \}$ for some $b \in \mathbb{Z}^+$. We can also see that $f(a) = g(b) = c$. Without loss of generality let $a \leq b$. $f(a) \neq a \implies f(a) \geq a + 1$. So, let $k \in \mathbb{Z}^+$ such that $f(k) = f(a) - 1$. Then $f(a) = f(g(k))$, but we see that $f(f(x)) = f(f(y)) \implies f(x) = f(y)$ ($f$ is injective over its images) implies that $a = g(k) \geq b$, so $a = b$. Therefore, we see that if $f(a) \geq a + 2$, then choose $k$ such that $f(k) = f(a) - 2$, then $f(g(g(k)) = f(k) + 2 = f(a) \implies a = g(g(k)) = g(f(y)) = g(y) + 1$ for some $g \in \mathbb{Z}^+$, a contradiction. Therefore $f(a) = a+1$ and similarly $g(a) = a+1$. Using strong induction, it is easy to see that $f(x) = g(x) = x +1$ for all $x \geq a$. Now, we see that given $x < a$, we have $f(f(x)) = f(x) + 1 = f(g(x))$, and since $f$ is injective over images, we have $f(x) = g(x)$ as desired.

Label the equation \begin{align} f(g(n))&=f(n)+1\\ g(f(n))&=g(n)+1 \end{align}Claim 1. $f(a)=f(b)\iff g(a)=g(b)$ Proof. If $f(a)=f(b)$, then $$g(a)=g(f(a))-1=g(f(b))-1=g(b)$$the other direction is similar. $\blacksquare$ Claim 2. Let $c_f=\min\text{ range f}$ and $c_g=\min\text{range g}$ and let $c=\max\{c_f,c_g\}$. Then the restriction of $f,g$ onto $\{c,c+1,...\}$ is injective. Proof. Suppose $f(a)=f(b)$ where $a,b\geq c$, then there exists $a_1,b_1$ such that $g(a_1)=a, g(b_1)=b$. Then from $(1)$, $$f(a_1)=f(g(a_1))-1=f(a)-1=f(b)-1=f(g(b_1))-1=f(b_1)$$hence $g(a_1)=g(b_1)$ from Claim 1, and so $a=b$ as desired. $\blacksquare$ Claim 3. $f(n)=g(n)=n+1$ for sufficiently large $n$ Proof. Pick a sufficiently large $d$, by Claim 2, there exists unique integers $x_i$ satisfying $$g(x_i)=d+i$$moreover, from Claim 2 we also deduce that sufficiently large integer all belongs to the sequence $x_i$ (since a number $x$ does not belong to the sequence if and only if $f(x)\leq d$, which can only occur for finitely many times by injectivity). Therefore, for sufficiently large integer, there exists $b_i$ for all $i\in \mathbb N$ such that $$x_{b_i}=e+i$$Now by $(2)$ we have $f(x_i)=x_{i+1}$. Pick sufficiently large $i$ s.t. $d+b_i\geq 1+e$, and sub. $n=x_{b_i-1}$ into $(1)$, then $$f(g(n))=f(d+b_i-1)=f(x_{b_{d+b_i-1-e}})=x_{b_{d+b_i-1-e}+1}$$while $$f(n)+1=x_{b_i}+1=x_{b_i+1}$$hence $b_{d+b_i-1-e}+1=b_i+1$ and so $d+b_i-1-e=i$, which implies $b_i-i$ is a fixed number for all sufficiently large $i$. This implies $g(x)-x$ is eventually constant. Suppose this constant is $k$, then $$f(n+k)=f(n)+1$$for sufficiently large integer $n$, hence $k=1$ by injectivity. (obviously $k>0$, but if $k>1$ then $f(n+1)=f(n+ak)$ for some $a$, contradiction). $\blacksquare$ Claim 4. range $f$=range $g$ Proof. By Claim 3, we have $$f(n)=n+1$$for all $n\geq N$, it suffices to show $\min$ range $f$= $\min$ range $g$. WLOG assume $M\min$ range $f$\leq $\min$ range $g=M+k$. Let $f(a)=M$, then $$f(g^m(a))=M+m$$Hence $g(a),g^2(a),...,g^{N-M}(a)$ must be distinct numbers in the range $[M+k,...,N-1]$, hence $k=0$ as desired. Claim 5. $f(M)=M+1=g(M)$ Proof. Notice by Claim 2 and 3, $f,g$ map $\{M,M+1,...,M+N-1\}$ bijectively to the set $\{M+1,...,N\}$. Pick $k$ such that $g(M+k)=M+1$, if $k\neq 0$ then there exists $m$ with $f(M+m)=M+k$. Then $$M+1=g(f(M+m))=g(M+m)+1$$hence $g(M+m)=M$, contradiction. $\blacksquare$ Then by induction it is easy to see $f(n)=n+1=g(n)$ for all $n\geq M$. Hence $f(g(n))=g(n)+1$, from $(1)$ we have $f(n)=g(n)$ as desired.

Claim 1: $f(m)=f(n)\Leftrightarrow g(m)=g(n)\Leftrightarrow f(f(m))=f(f(n))\Leftrightarrow g(g(m))=g(g(n))$ $f(m)=f(n)\Leftrightarrow g(m)=g(n)$ follows trivially by plugging $m,n$ into the given equations. If $f(f(m))=f(f(n))$, then: $$g(n)+2=g(f(n))+1=g(f(f(n)))=g(f(f(m))=g(f(m))+1=g(m)+2,$$and our four-way equivalence follows. Claim 2: $\operatorname{Im}(f)=\mathbb N_{\ge a}$ and $\operatorname{Im}(g)=\mathbb N_{\ge b}$ for some $a,b\in\mathbb N$ We can show that $f(g^k(n))=f(n)+k$ and $g(f^k(n))=g(n)+k$ for $n,k\in\mathbb N$ through induction: If $f(g^k(n))=f(n)+k$, then $f(g^{k+1}(n))=f(g(n))+k=f(n)+k+1$. The base case is trivial, and proving it for $g$ is also trivial. Now let $a=\min(\operatorname{Im}(f))$ and $b=\min(\operatorname{Im}(g))$. By this, $a+k\in\operatorname{Im}(f)$ and $b+k\in\operatorname{Im}(f)$ for $k\in\mathbb N$ from which we deduce that $\operatorname{Im}(f)=\mathbb N_{\ge a}$ and $\operatorname{Im}(g)=\mathbb N_{\ge b}$. Claim 3: $f(a)\ge a+1$ and $g(b)\ge b+1$ We already have that $f(a)\ge a$ and $g(b)\ge b$. If $f(a)=a$, then $g(a)=g(f(a))=g(a)+1$, and we reach a similar contradiction if $g(b)=b$. Claim 4: $a=b$ Since $f(a)\ge a+1$, $f(a)-1\in\operatorname{Im}(f)$, so let $f(p)=f(a)-1$. WLOG $a\le b$, so $g(p)\ge a$. Then: \begin{align*}f(g(p))&=f(p)+1\\f(g(p))&=f(a)\\g(p)&=a\end{align*}Thus $a\ge b$. Combining $a\ge b\ge a$ gives $a=b$. Claim 5: $f(x)=g(x)=x+1\forall x\ge a$ We prove this by induction: Base case: Assume $f(a)\ge a+2$ and let $f(q)=f(a)-2$. The same as before, we have: $$f(g(g(q)))=f(g(q))+1=f(q)+2=f(a)\Rightarrow g(g(q))=a.$$Letting $g(q)=f(r)$, we obtain $a=g(f(r))=g(r)+1\ge a+1$, contradiction. Then $f(a)$ must be $a+1$, and similarly $g(a)=a+1$. Induction step: If $f(x)=g(x)=x+1$ for some $x$, then $f(x+1)=f(g(x))=f(x)+1=x+2$ and $g(x+1)=g(f(x))=g(x)+1=x+2$. Finally, $g(n)\ge a$ implies $f(n)+1=f(g(n))=g(n)+1$, and so $f(n)=g(n)$.

Denote $\underbrace{f(f(\ldots f(x)\ldots ))}_k=f^k(x)$. It is easy to prove by induction the following relations: \begin{align} f(g(n)+k)=f^{k+1}(n) +1\\ g(f(n)+k)=g^{k+1}(n)+1\\ f(g^k(n))=f(n)+k\\ g(f^k(n))=g(n)+k \end{align}Denote $f^k(n)=a_n$ and $g^k(n)=b_n$.WLOG $a_1\ge b_1$. From $(3)$ and $(4)$: $$f(b_k)-g(a_k)=a_1-b_1=c\ge 0, \forall k \in \mathbb{N}$$Now $(1)-(2)\Rightarrow f(b_1+k)-g(a_1+k)=c, \forall k \in \mathbb{N}.$ Take $k\rightarrow k-a_1:$ $$f(k-c)=c+g(k), \forall k\ge a_1.$$Finally, consider $c_0\ge a_1$ so that $f(f(c_0))$ is minimal. Put $k\rightarrow c_0+c\Rightarrow f(c_0)=c+g(c_0+c)$. Hence $$f(f(c_0))=f(g(c_0+c)+c)=f^{c+1}(c_0+c)+1$$which, by $f(f(c_0))$'s minimality, leads to $c=0\Leftrightarrow f=g$, and we are done.

Solved with rama1728. It's not hard to verify $g(g(m)) = g(g(n)) \iff f(m) = f(n) \iff g(m) = g(n) \iff f(f(m)) = f(f(n))$ by plugging in $g(m), f(n), m, n$ into the equations. Also note that $f(n) , g(n) \ne n.$ Note that if $c$ is in the image of $f,$ so is $c+1.$ So let $\{a,a+1, \dots \}$ and $\{b,b+1, \dots \}$ be the images of $f$ and $g$ respectively for positive integers $a,b.$ Obviously $f(a) \ge a+1$ and $g(b) \ge b+1.$ So there exists a $c$ where $f(c)+1= f(a).$ So $f(g(c)) = f(a).$ Assume $b \ge a,$ then $g(c) \ge b \ge a$ so $g(c), a$ are both in the image of $f(n).$ This implies $g(c) = a,$ so $a \ge b$ and $\{a,a+1, \dots \}$ is the image of both functions. Suppose $f(a) \ne a+1.$ So there exists a $c$ where $f(c) +2 = f(a).$ So $f(g(g(c))) = f(g(c)) + 1 = f(c) + 2 = f(a).$ Since $g(g(c)), a$ are both in the image of $f,$ we have $g(g(c)) = a.$ There exists some $d$ where $g(c) = f(d),$ so $g(g(c)) = g(f(d)) = g(d) + 1,$ so $g(d) = a-1,$ contradiction. So $f(a) = a+1.$ Similarly, $g(a) = a+1.$ By induction, we can easily prove that $f(n) = n+1$ for all $n \ge a.$ Take any $n.$ Note that $f(g(n)) = f(n)+1,$ but since $g(n) \ge a, f(g(n)) = g(n)+1$ as desired. $\square$

We start by observing some results that are trivial to prove. $f(x)=f(y)\iff g(x)=g(y).$ $f(g^i(x))=f(x)+i ~~\forall i\in \mathbb{Z^+}$ and $g(f^i(x))=g(x)+i ~~\forall i \in \mathbb{Z^+}.$ $\exists x_1,y_1 \in \mathbb{Z^+}: x_1=\min(\text{Im}(f))$ and $y_1=\min(\text{Im}(g)).$ $f(f(x))=f(f(y))\implies f(x)=f(y).$ Claim 1: $x_1=y_1.$ Proof. Assume the contrary. WLOG $x_1\leq y_1.$ It follows $g(y_1)\geq y_1+1.$ Let $g(z)=g(y_1)-1.$ So $g(y_1)=g(z)+1\implies g(f(z))=g(y_1)\implies f(z)\geq x_1 \geq y_1 \implies x_1=y_1.$ Q.E.D. $\blacksquare$ Claim 2: $f(x_1)=x_1+1$ (Same argument holds for $g(y_1)=y_1+1.$) Proof. Assume the contrary that $f(x_1)\geq x_1+2.$ $\exists a,b \in \mathbb{Z^+}: f(a)=f(x_1)-2$ and $f(b)=g(a).$ It follows that, $f(x_1)=f(a)+2\implies f(g^2(a)) \implies x_1=g^2(x_1)=g(f(b))=g(b)+1 \geq 1+ x_1,$ a contradiction. $\blacksquare$ Claim 3: $f(x)=g(x)\forall x\in \mathbb{Z^+}.$ Proof. It follows by induction that $f(x)=g(x)=x+1.$ So $g(x)\geq x_1 \implies f(x)+1=f(g(x))=g(x)+1.$ Thus we're done. $\blacksquare$

Note that both $f$ and $g$ satisfy that if $x$ is in the image, then $x+1$ is. Let the image of $f$ be $\{a,a+1,a+2,\ldots, \}$ and the image of $g$ be $\{b,b+1,b+2,\ldots, \}$. WLOG that $a\ge b$. We can check that 1) $f(g^k(n)) = f(n) + k$, 2) $g(f^k(n)) = g(n) + k$ 3) $g(f(n) + k) = g^{k+1}(n) + 1$ 4) $f(g(n)+k) = f^{k+1}(n) + 1$. If $g(g(m)) = g(g(n))$, then by 1), we have $f(m) = f(n)$, so $g(f(m)) = g(f(n))$, which implies $g(m) = g(n)$. Let $g(g(m))= g(g(n)) \implies g(m) = g(n)$ be denoted as $*$. If $f$ or $g$ had any eventual cycles (as in $f^k(n) = n$ for some $k$), this would either contradict 1) or 2). So $f$ and $g$ don't have any eventual cycles. Since $f(a)\ne a$, $g(b)\ne b$, $f(a)\ge a+1$ and $g(b)\ge b+1$. There exists a positive integer $m$ such that $g(m) = g(b) - 1$. We have $g(f(m)) = g(b)$. Since $f(m)$ and $b$ are in the image of $g$, we have $f(m) = b$, so $b\ge a$. Thus, $a=b$. Claim: $n\ge a+k$ implies $f(n) \ge a+k+1$ for all nonnegative integers $k$. Proof: We prove this result by induction on $k$. Base case: For any $n\ge a$, we can set $x$ such that $g(x) = n$, so $f(n) = f(x) + 1\ge a+1$. Inductive step: Suppose the result is true for all $k< x$. We have for any positive integer $n$, \[f(n)\ge a, f(f(n))\ge a+1, \ldots, f^{x+1}(n)\ge a+x\] So $f(g(n)+x) \ge a+x+1$. Since $g(n)+x$ can take any positive integer value at least $a+x$, we have $n\ge a+x$ implies $f(n)\ge a+x+1$, as desired. \end{proof} So $f(n)\ge n+1$ for all $n\ge a$. Similarly, we can prove $g(n)\ge n+1$ for all $n\ge a$. Since $g(n)\ge a$, we have $f(n) + 1 = f(g(n)) \ge g(n) + 1$, so $f(n)\ge g(n)$. Since $f(n)\ge a$, we have $g(n)+1 = g(f(n)) \ge f(n)+1$, so $g(n)\ge f(n)$. Thus, $f(n) = g(n)$.

Note that if $y$ is in the range of $f$, say $f(x)=y$, then so is $y+1$ from $f(g(x))=f(x)+1=y+1$. Thus, the range of $f$ and $g$ are in the form $\{a,a+1,\dots,\}$ and $\{b,b+1,\dots,\}$, respectively. Suppose $f(x)=x$, then $g(x)=g(f(x))=g(x)+1$, absurd. In particular, $f(a)\ge a+1$ and similarly $g(b)\ge b+1$. WLOG, assume $a\ge b$. Since $g(b)\ge b+1$, we have for some $x$ that $g(b)=g(x)+1=g(f(x))$. Since $f(x)\ge a\ge b$, $f(x)$ is in the range of $g$, so let $b=g(y)$ and $f(x)=g(z)$. We have $g(g(y))=g(g(z))$ so $f(g(g(y)))=f(g(g(z)))$. Thus, $f(g(y))=f(g(z))$ which implies $f(y)=f(z)$. We can write $g(f(y))=g(f(z))$ to get $g(y)=g(z)$. Thus, $f(x)=b$, and so $a=b$. The ranges of $f$ and $g$ are the same. Suppose $f(a) \ge a+2.$ Let $p$ be such that $f(a)=f(p)+2$. We have \[f(g(g(p)))=f(g(p))+1=f(p)+2=f(a)\]Let $g(g(p))=f(q)$ for some $q$, and $a=f(r)$ for some $r$, and we have $f(f(q))=f(f(r))$ which similarly as above gives $f(q)=f(r)$, so $g(g(p))=a$. Additionally, we can let $g(p)=f(s)$ so \[a-1=g(g(p))-1=g(f(s))-1=g(s)\]absurd. Thus, $f(a)=a+1$, $g(a)=a+1$. If $f(n)=g(n)=n+1$ then $f(n+1)=f(g(n))=f(n)+1=n+2$ and similarly for $g$. Thus, $f(n)=n+1$ for all $n\ge a$. Hence, $f(g(n))=g(n)+1$ so $f(n)=g(n)$.

Note that images of compositions of $f$ and $g$ are upwards closed. Let \begin{align*} \text{Im}(f) &= \{f_0, f_0 + 1, \dots\} \\ \text{Im}(g) &= \{g_0, g_0 + 1, \dots\} \end{align*}be the images of $f$ and $g$ respectfully. By the condition, \begin{align*} \text{Im}(f \circ g^k) = \{f_0 + k, f_0 + k + 1, \dots\} \\ \text{Im}(g \circ f^k) = \{g_0 + k, g_0 + k + 1, \dots\} \end{align*}It then follows that since the above images shrink in size as $k$ increases, that is \begin{align*} \text{Im}(f) \supsetneq \text{Im}(f^2) \supsetneq \dots&\\ \text{Im}(g) \supsetneq \text{Im}(g^2) \supsetneq \dots&\\ \end{align*}so \begin{align*} \text{Im}(f^k) &\subseteq \{f_0 + k - 1, \dots\} \\ \text{Im}(g^k) &\subseteq \{g_0 + k - 1, \dots\} \end{align*}and it follows that \begin{align*} \text{Im}(g \circ f \circ g^k) \subseteq \{g_0 + k + 1, \dots\} \\ \text{Im}(f \circ g \circ f^k) \subseteq \{f_0 + k + 1, \dots\} \\ \end{align*}Then $n \ge f_0 + k \implies g(n) \ge g_0 + k + 1$ implies that \[ f(n) \ge f_0 + k \implies g(n) \ge g_0 + k \]which holds two way by symmetry. As such, $g(n) \ge g_0 + f(n) - f_0$ and $f(n) \ge f_0 + g(n) - g_0$ which means that $f(n) - f_0 = g(n) - g_0$ Then $g(f(n)) = g(n) + 1$ is equivalent to $f(f(n)) = f(n) + 1$ and by symmetry $g(g(n)) = g(n) + 1$ holds. Thus, $f(n + 1)$ equals $f(n) + 1$ on $\text{Im}(f)$, same for $\text{Im}(g)$ Then, if we take $k \in \text{Im}(f) \cup \text{Im}(g)$, then $f(k) - f_0 = g(k) - g_0$ implies $f_0 = g_0$ and thus $f(n) = g(n)$.

Lemma 1. $f(n)\ne n$ and $g(n)\ne n$ for all positive integers $n$. Proof. Suppose $f(t)=t$ for some positive integer $t$. Then $g(t)+1=g(f(t))=g(t)$, contradiction. Similarly, $g(n)\ne n$ for all positive integers $n$. $\square$ Lemma 2. For all $n\in\mathbb N$, we have $$n\in f(\mathbb N)\implies n+1\in f(\mathbb N)$$and $$n\in g(\mathbb N)\implies n+1\in g(\mathbb N).$$ Proof. Suppose $n\in f(\mathbb N)$. Then $n=f(m)$ for some integer $m$, so $$n+1=f(m)+1=f(g(m))\in f(\mathbb N).$$A similar argument holds for $g$. $\square$ Lemma 3. Let $A=\min(f(\mathbb N))$ and $B=\min(g(\mathbb N))$. Then $A=B$. As a result, $f(\mathbb N)=g(\mathbb N)$. Proof. WLOG, assume $A\ge B$. By lemma 1 we have $g(B)\ge B+1$. Therefore, by lemma 1, $g(B)-1=g(t)$ for some $t\in\mathbb N$ so $$g(B)=g(t)+1=g(f(t)).$$Pick a positive integer $u$ such that $g(u)=B$. As we assumed $A\ge B$ and by lemma 2, the number $f(t)$ is in the range of $g$ so $f(t)=g(v)$ for some $v\in\mathbb N$. Thus, $$g(g(u))=g(B)=g(f(t))=g(g(v)).$$It follows that: $$f(g(g(u)))=f(g(g(v)))$$$$\implies f(g(u))=f(g(v))$$$$\implies f(u)=f(v)$$$$\implies g(f(u))=g(f(v))$$$$\implies g(u)=g(v)$$It follows that $B=g(u)=g(v)=f(t)$. Hence $B\in f(\mathbb N)$ so $A=B$. $\square$ Lemma 4. Let $A=\min(f(\mathbb N))=\min(g(\mathbb N))$ from lemma 3. Then $f(A)=g(A)=A+1$. Proof. By lemma 1 we know that $f(A)\ge A+1$. Assume $f(A)\ge A+2$. By lemma 2, there exists $t\in\mathbb N$ such that $f(A)-2=f(t)$. Thus, $$f(A)=f(t)+2=f(t)+1+1=f(g(t))+1=f(g(g(t))$$By lemma 3, there exists $u\in\mathbb N$ such that $g(u)=A$, so $$f(g(g(t))=f(g(u))$$$$\implies f(g(t))=f(u)$$$$\implies g(f(g(t))=g(f(u))$$$$\implies g(g(t))=g(u)=A.$$Now $g(t)$ is in the range of $f$ so $g(t)=f(v)$ for some $v\in\mathbb N$. Hence $$A=g(g(t))=g(f(v))=g(v)+1\ge A+1$$which is a contradiction. It follows that $f(A)=A+1$. Similarly, $g(A)=A+1$. $\square$ Lemma 5. We have $f(n)=g(n)=n+1$ for all $n\ge A$. Proof. We will prove the result by induction on $n$. The base case $n=A$ was proven in lemma 4. Now suppose $k\ge A$ and $f(k)=g(k)=k+1$. Then the induction hypothesis implies that $$f(k+1)=f(g(k))=f(k)+1=k+2.$$Similarly, $g(k+1)=k+2$. $\square$ Now, to finish, pick an arbitrary $n\in\mathbb N$. As $f(n)\ge A$, lemma 4 implies that $$f(n)+1=g(f(n))=g(n)+1.$$Thus, $f(n)=g(n)$ for all positive integers $n$.

We begin with some basic observations. Notice that $f(g^k(x)) = f(g^{k-1}(x))+1 = f(g^{k-2}(x))+2 = \dots = f(x)+k$, and similarly $g(f^k(x))=g(x)+k$. Next, observe that $f(x) = f(y)$ implies $g(x) = g(f(x))-1 = g(f(y))-1 = g(y)$. Obviously, the convsrse must also hold. (1) Now, assume that $x, y \in \mathbb{Z}_{>0}$ satisfies $f(f(x)=f(f(y))$. By (1), we get that $g(x)=g(f(x))-1=g(f(y))-1=g(y) \ \Rightarrow \ f(x)=f(y)$ (2) Let $a$ be the smallest value attained by f. Take $f(x) = a$. We have $f(g^k(x)) = f(x)+k = a+k$. Therefore, $a+k$ is in the range of $f$ for all nonnegative integers $k$. So, we must have $\ \text{Im} \ f = \{a, a+1, a+2 \ \ldots \ \} $. Similarly, there must exist a positive integer $b$ such that $\text{Im} \ g = \{b, b+1, b+2 \ \ldots \ \}$ (3) Claim 1: $a=b$ Assume WLOG that $a \leq b$. If $f(a)=a$, we have $g(a)=g(f(a))=g(a)+1$ contradiction. So, we must have $f(a) > a$. Then, by (3), there exists a positive integer $k$ such that $f(k)=f(a)-1$. Note that $f(a)=f(k)+1=f(g(k))$. Now, notice that since $a$ and $g(k)$ are in the range of $f$ we must have $g(k)=a$ by (2). Therefore, $b \leq a \ \Rightarrow \ a=b$. $\square$ Claim 2: $\ \text{Im} \ f^k = \{a+k-1, a+k, a+k+1 \ \ldots \ \} = \ \text{Im} \ g^k$ We use induction on $k$. The base case follows from Claim 1. Assume the claim is true for $k-1$. Fix an arbitrary positive integer $n$. We know that there is a positive integer $m$ satisfying $f^{k-1}(n)=g^{k-1}(m)$. Then, we have $f^k(n)=f(g^{k-1}(m))=f(m)+k-1 \geq a+k-1$. Now, consider an arbitrary positive integer $d$ greater than $a+k-2$. We know that there are positive integers $a, b, c$ such that $d=f^{k-1}(a)+1, \ f^{k-2}(a)=g^{k-2}(b), \ g^{k-1}(b)=f^{k-1}(c)$. Then, we have $d=f^{k-1}(a)+1=f(g(f^{k-2}(a)))=f(g^{k-1}(b))=f^k(c)$. Therefore, $\ \text{Im} \ f^k = \{a+k-1, a+k, a+k+1 \ \ldots \ \}$. Using a similar argument we can show the result on $g$. $\square$ It follows from Claim 2 that $f(x)>x$ and $g(x)>x$ for all $x \in \mathbb{Z}_{>0}$. (4) Now, consider the sequence $A_x = \{f(x), f^2(x), \ \ldots \ \}$ for an arbitrary positive integer $x$. Claim 3: $A_x$ contains all sufficiently large positive integers. Consider a sufficiently enough positive integer $n$. Notice that $g(n)>n>g(x)$ Let $g(n)=g(x)+k$. Then, we have $g(f^k(x))=g(x)+k=g(n) \ \Rightarrow \ f^{k+1}(x)=f(n)$ by (1). Therefore, there is a constant positive integer $N$ such that all $f(n)$ satisfying $n>N$ is contained in $A_x$. Since it is clear that the set $\{f(n) \mid n>N\}$ contains all sufficiently large positive integers we are done. $\square$ Claim 4: $f(n)=n+1$ for all sufficiently large $n$. Consider a sufficiently large positive integer $n$. By Claim 3, it suffices to show that $f^{n+1}(x)=f^n(x)+1$. Assume the contrary. Then, we have $f^n(x)+1 \neq f^{n+1}(x) > f^n(x) \ \Rightarrow \ f^{n+1}(x) > f^n(x)+1$. Now, Claim 3 tells us that there is a positive integer $s$ such that $f^s(x)=f^n(x)+1$. Notice that if $s \leq n$ we have $f^s(x) \leq f^n(x)$ contradiction. So, we must have $s > n$. But then, by (4) we get $f^s(x) \geq f^{n+1}(x) > f^n(x)+1$ a contradiction. Similarly, $g(n)=n+1$ for all sufficiently large n. $\square$ Claim 5: $f(n)=n+1=g(n)$ for all $n \geq a$. We use downward induction. Assume that $f(k)=k+1=g(k)$ for all $k \geq n$ and there is a positive integer $m$ satisfying $f(m)=n-1$. Or, in other words, $n-1 \geq a$. Suppose for contradiction $f(n-1) \neq n$. Then, we have $f(n-1) > n \ \Rightarrow \ f(n-1)=f(f(n-1)-1)$ and $f(n-1)-1 \neq n-1$. Let $f(k)=f(n-1)-1$. Then, we have $f^2(m)=f^2(k)$. Now, applying (2), we get $n-1=f(m)=f(k)=f(n-1)-1 \ \Rightarrow \ f(n-1)=n$. We use the same argument for $g$. $\square$ Consider an arbitrary positive integer $n$. By Claim 5, we know that $f(n)+1=g(f(n))=g(n)+1 \ \Rightarrow \ f(n)=g(n)$ and hence we are done. $\blacksquare$

Our conditions can be extended to $f(g^k(n))=f(n)+k$ and $g(f^k(n))=g(n)+k$. Suppose the minimal values in the ranges of $f$, $g$ are $a = f(m)$, $b = f(n)$, respectively. The extended conditions tell us every natural greater than the mins of $f$ and $g$ are in their respective ranges. Note that $f(x)=f(y) \iff g(x)=g(y)$, as \[g(x)+1 = g(f(x)) = g(f(y)) = g(y)+1,\]and analogously for the other direction. Denote this $\emph{similarity}$ relationship as $x \sim y$. Define $S_x$ as the set of values similar to $x$. Note that \[f(x) \sim f(y) \implies g(f(x))=g(f(y)) \implies g(x)+1=g(y)+1 \implies f(x) = f(y).\]This tells us $S_t$, where $t$ is in the range of $f$, cannot contain another element in the range of $f$ other than $t$, and similarily for $g$. We now further analyze our minimal values. We focus on $f$, with results on $g$ completely analogous. $f(a)=a$ cannot satisfy our second condition, so $f(a) \ge a+1$. WLOG $a \ge b$. From the previous, there exists a $k$ such that $f(k) = f(a)-1$, which means \[f(g(k))=f(a) \implies a \sim g(k) \implies a = g(k) \ge b \implies a=b.\] FTSOC suppose $f(a) \neq a+1$. Then there exists $u$, $v$ with $f(u) = f(a)-2$ and $f(v) = g(u)$. Then $f(a)=f(g^2(u))$, which is a contradiction as this implies \[a \sim g^2(u) \implies a = g^2(u) = g(v)+1 \ge a+1.\] A quick induction then shows $f(x)=g(x)=x+1$ for all $x \ge a$. We finally conclude by noting $f(x)=c$ for all $c$ in the (mutual) ranges of $f$, $g$ implies \[c+1 = g(c) = g(x) + 1 \implies g(x)=c \implies f = g. \quad \blacksquare\]

Wonderful Problem! Gsolve with orz taptya17 First of all notice we can do same type of manipulation with $g$ which we do with $f$ each time. Assume $f(x) \geq m_1$ and $g(x) \geq m_2$ for all $x \in \mathbb{N}$. Also $f(u_1)=m_1$ and $g(u_2)=m_2$ (If there are multiple such $u's$ we will choose one of them). Now by using $(1)$ $a$ times, we get $$f(g^{a-m_1}(u_1))=f(u_1)+a-m_1=a$$and similarly for $g$. So we can get all $f^{-1}(x)$ for $x \geq m_1$. Claim: We can't have $g(a)=g(b)$ for $a,b \geq m_2$. If $f(a)=f(b)$ then $$g(f(a))=g(a)+1=g(f(b))=g(b)+1 \rightarrow g(a)=g(b)$$Also $f(n)=n$ can't possible, as we get $0=1$. From $(2)$ So we have $$g(g(f^{a-m_2}(u_2)))=g(g(f^{b-m_2}(u_2))) \Rightarrow f^{a-m_2}(u_2)=f^{b-m_2}(u_2)=k$$But now if $b > a$ then $f^{b-a}(k)=k$. But then we will get $g(f^{a-b}(k))=g(k)+a-b \Rightarrow a-b = 0$. So only way is $a=b$. Claim: $$m_1=m_2.$$$$g(m_2) = g(f^{g(m_2)-m_2}(u_2))$$So we get $m_2=f^{g(m_2)-m_2}(u_2)$ or $ m_2 > f^{g(m_2)-m_2}(u_2)$. But then if $m_2 < m_1$ we can't get $f^{g(m_2)-m_2}(u_2) < m_2$ where $f \geq m_1$. Hence $m_1 \leq m_2$. But doing same things for $f$ we get $m_2 \leq m_1$. Therefore $m_1=m_2=m$. We get $f^{g(m)-m}(u_2)=m$. Now as in $f(g(n))=f(n)+1$ , $g(n)$ can take value $m \geq$ we will always have $f(x) \geq m+1$ for $x \geq m$. Hence only way to get $f^{g(m)-m}(u_2)=m$ is $g(m)=m+1$. Similarly $f(m)=m+1$. Now apply this $f(g(m))=f(m)+1 \Rightarrow f(m+1)=f(m)+1$. Similarly we get $f(x)=g(x)=x+1$ for $x \geq m$. Now if $f(k)=h$ for $k <m$. Then $g(f(k))=g(k)+1 \Rightarrow g(h)=g(k)+1$ as $h \geq m$ we should have $g(h) = h+1 = g(k)+1$, which give us $g(k)=f(k)$. Hence $f(n)=g(n)$ for all positive $x$. Hence $f \equiv g$.

We work on the images of $f$, $g$ under subsets of $\mathbb{N}$. Define the shorthand $S_k = \{k, k+1, k+2, \dots\}$. Claim: If $k \in f(\mathbb{N})$, then $k+1 \in f(\mathbb{N})$. Proof. $k + 1 = f(x) + 1 = f(g(x))$ for some $x$. Hence we obtain $f(\mathbb{N}) = S_a$ and, by symmetry, $g(\mathbb{N}) = S_b$ for some $a$, $b$. Claim: $a=b$. Proof. We have: \begin{align} f(S_b) = f(g(\mathbb{N})) &= f(\mathbb{N}) + 1 = S_{a+1} \\ g(S_{a+1}) = g(f(S_b)) &= g(S_b) + 1 \end{align}Now this implies $g(S_{a+1}) \not\subseteq g(S_b)$, so $a+1 > b$. By symmetry, $b+1 > a$, so we're done. Claim: For all $k \geq a$, we have $f(S_k) = g(S_k) = S_{k+1}$. Proof. Induct on $k$. Equation $(1)$ and its symmetric counterpart give us the base case $f(S_a) = g(S_a) = S_{a+1}$. For the induction step: \[ f(S_{k+1}) = f(g(S_k)) = f(S_k) + 1 = S_{k+2} \]By symmetry, $g(S_{k+1}) = S_{k+2}$, and we're done. Now for all $k \geq a$ we have $f(S_{k+1}) / f(S_k) = \{k+1\}$, so $f(k) = k+1$. Combine this with $g(n) \geq a$ for all $n$; we have \[ f(n) + 1 = f(g(n)) = g(n) + 1\]for all $n$, as desired.