#8 Iteration

If \(f(a)=a\), then \(f(f(a))=f(a)=a\). But by the condition, \(f(f(a))=a+1\). This gives the contradiction \(a=a+1\).

Let \(y\) be in the image. Then \(y=f(t)\) for some \(t\). Therefore \(f(y)=f(f(t))=f(t)=y\). Hence \(y\) is fixed.

If \(f(a)>a\), increasingness gives \(f(f(a))>f(a)\), so \(a>f(a)\), contradiction. If \(f(a)

We have \(f(f(x))=a(ax+b)+b=a^2x+b(a+1)\). Thus \(a^2=1\) and \(b(a+1)=0\). If \(a=1\), then \(b=0\), giving \(f(x)=x\). If \(a=-1\), then \(b\) is arbitrary, giving \(f(x)=-x+b\).

The cycles of the permutation have lengths \(1\) or \(3\). If there are no fixed points, all cycles have length \(3\), so the number of elements is divisible by \(3\). But \(10\) is not divisible by \(3\). Hence there is a cycle of length \(1\), i.e. a fixed point.

Let \(f(x)=cx\). Then \(f(f(x))=c^2x\). We get \(c^2=4\), so \(c=2\) or \(c=-2\). The answer is \(f(x)=2x\), \(f(x)=-2x\).

Additivity on \(\mathbb Q\) gives \(f(x)=cx\). The condition \(f^3(x)=8x\) gives \(c^3=8\), hence \(c=2\). The answer is \(f(x)=2x\).

We have \(f^2(x)=a^2x+b(a+1)\). Thus \(a^2=1\). If \(a=1\), then \(2b=6\), so \(b=3\). If \(a=-1\), the shift is \(0\), not \(6\). The answer is \(f(x)=x+3\).

The coefficient of \(x\) in \(f^3(x)\) is \(a^3\), so \(a^3=1\), hence \(a=1\). Then \(f(x)=x+b\), and \(f^3(x)=x+3b\). We get \(3b=6\), so \(b=2\). The answer is \(f(x)=x+2\).

If \(P\) is constant, impossible. If \(\deg P=d\), then \(d^2=1\), so \(d=1\). Let \(P(x)=ax+b\). Then \(a^2x+b(a+1)=x\), hence \(a^2=1\), \(b(a+1)=0\). The answer is \(P(x)=x\) or \(P(x)=-x+b\).

Every constant polynomial works. Let \(P\) be nonconstant. Then the image of \(P\) is infinite. For every \(t=P(x)\), we have \(P(t)=t\). Thus the polynomial \(P(T)-T\) has infinitely many roots, so \(P(T)=T\). The answer is all constant polynomials and \(P(x)=x\).

Cycle lengths can be \(1,2,4\). If there are no cycles of length \(1\) or \(2\), then all cycles have length \(4\). Hence the number of elements must be divisible by \(4\), but \(6\) is not divisible by \(4\). Contradiction.

From \(f(n+1)=f(n)+1\), the value \(f(n)-n\) is constant on \(\mathbb Z\). Hence \(f(n)=n+c\). Then \(f^2(n)=n+2c\). The condition gives \(2c=4\), so \(c=2\). The answer is \(f(n)=n+2\).

Let \(m=f(n)\). Then \(m>n\), and \(f(m)=n+2\). Applying the condition to \(m\), we get \(f(m)>m\). Hence \(n+2>m\). Thus \(n

For all \(x\), \(a^2x\equiv x\pmod p\), so \(a^2\equiv1\pmod p\). Thus \((a-1)(a+1)\equiv0\pmod p\). Since \(p\) is prime, \(a\equiv1\) or \(a\equiv-1\pmod p\).

If \(P\) is constant, impossible. Let \(\deg P=d\). Then \(\deg P^3=d^3\), while the right-hand side has degree \(1\), so \(d=1\). Let \(P(x)=ax+b\). The coefficient of \(x\) in the third iterate is \(a^3\), so \(a^3=1\), hence over \(\mathbb R\), \(a=1\). Then \(P(x)=x+b\), and \(P^3(x)=x+3b\). Thus \(b=0\). The answer is \(P(x)=x\).

Additivity on \(\mathbb Q\) gives \(f(x)=cx\) with rational \(c\). Then \(f(f(x))=c^2x\). The condition requires \(c^2=-1\), impossible for a rational number. Hence no such function exists.

If \(P=c\) is constant, then \(c=c^2\), so \(c=0\) or \(c=1\). Let \(P\) be nonconstant. For every \(t\) in the image of \(P\), we have \(t=P(x)\), hence \(P(t)=t^2\). The image of a nonconstant polynomial is infinite, so \(P(T)-T^2\) has infinitely many roots. Therefore \(P(T)=T^2\). The answer is \(P=0\), \(P=1\), \(P(x)=x^2\).

If \(f(a)>a\), increasingness gives \(f^2(a)>f(a)>a\), and then \(f^3(a)>f^2(a)>a\), contradicting \(f^3(a)=a\). If \(f(a)

Fix \(a\). If \(f(a)>a\), then strict increasingness gives \(f^2(a)>f(a)\), then \(f^3(a)>f^2(a)\), and so on. Thus \(f^k(a)>a\), a contradiction. If \(f(a)