Take $k\not= l$ and let $g$ be any function with $g(k)=k,g(l)=l$. The condition for $n=k,l$ and rewriting gives $$g(f(l))-g(f(k))=f(l)-f(k)$$If $f(k)\not \in \{f(l),k,l\}$ then we can give $g(f(k))$ any value, choosing a suitable $g$, and we have a contradiction. Also for $f(l)$ hence we see $f(k)=f(l)\vee f(k),f(l)\in \{k,l\}$. Then also $$f(k)=f(l)\vee \{f(k),f(l)\}=\{k,l\}$$Constant functions $f$ are solutions, otherwise we can choose $a,b$ with $f(a)\not=f(b)$. Then $\{f(a),f(b)\}=\{a,b\}$. Now suppose $m\not=a,b$. We know $f(m)\not =f(a)\vee f(m)\not= f(b)$ hence $\{f(m),f(a)\}=\{a,m\} \vee \{f(m),f(b)\}=\{b,m\}$. In both cases we have $f(m)=m$ and we also see $f(a)=a\vee f(b)=b$. Since $\{f(a),f(b)\}=\{a,b\}$ we see $f(a)=a,f(b)=b,f={\rm id}$. Hence we find two kinds of solutions, $f=c$ and $f=x$.

Take $g(n) = n+1$, so we get $f(n+1)-f(n)$ is constant, and thus $f$ is linear. Plugging back $f(x) = mx+n$ with $g(x) = x^2$ we see either $m = 0$ or $n = 0, m =1$, both of which are indeed solutions.

Can we consider $f(x)=g(x)$ as also a solution?

No, as $f(g(n)) - g(f(n))$ is constant on $n$ for any $g$ so $f\neq g$ as $f$ can't be defined as two functions at once.

After proving $f $ is linear. Plugging $f=gn+b $ and $f (z)=nz+b $ Let $n (t)=2t$, thus we get $b=0$ $f (z)=cz\implies f (z)=cz+b $ $n (t) $ is a function Take $n=1$, and $f (z)=z $

Attached below is the official solution that I found. Can someone help me understand these claims: (Second paragraph - "If there is no n_0..."): • How is $f(g(n_0))=f(0)$? • How does $g(f(n))=1$ imply $f(n)=f(n_0)$? (Third paragraph - "Now, consider the...") • I don't understand how we 'find' $f(g(f(n_0)))-g(f(f(n_0)))=f(g(n_0))-g(f(n_0))$ • How does $g(f(f(n_0))) = g(f(n_0)) = a$ imply $ f(f(n_0)) = f(n_0)$? It would be greatly appreciated if someone would elaborate on those clarifications

Attachments:

Let $P(g(n))$ be the given assertion. $P(n+1)\Rightarrow f(n+1)-f(n)$ is consant, so $f(x)=ax+b$ for some $a,b\in\mathbb Z$ $P(n^2)\Rightarrow an^2+b-a^2n^2-2abn-b^2$ is constant, so $a\in\{0,1\}$ and $ab=0$. This gives the solutions $\boxed{f(x)=x}$ and $\boxed{f(x)=c}$ which borth trivially work.