Oops

My solution to this one: If $a_{1}, a_{2},\ldots, a_{k}$ are points of a periodic orbit of $P$ ($P(a_{i})=a_{i+1}$) we have \[a_{2}-a_{1}\mid a_{3}-a_{2}\mid \ldots\mid a_{1}-a_{k}\mid a_{2}-a_{1}\] So we have $|a_{i+1}-a_{i}|$ is a constant. But this is impossible for $k>2$. (Guess why) So all periodic orbits are of degree $1$ or $2$. If we have no $2$nd degree periodic orbit we are done ($P(x)=x$ has at most $n$ roots) If we have two $2$nd degree orbits like $(a,b)$ and $(c,d)$, then we have \[a-c\mid b-d\mid a-c\] So we have $|a-c|=|b-d|$ and similarly $|a-d|=|b-c|$ which easily proves that $a+b=c+d$. If we have a $2$nd degree orbit like $(a,b)$ and a fixed point $t$ then similarly we would have $t+t=a+b$. So now let just $u=a+b$ then all periodic points are the roots of equation $x+P(x)=u$ which obviously has at most $n$ roots.

Nima Ahmadi Pour wrote: My solution to this one: If $a_{1}, a_{2},\ldots, a_{k}$ are points of a periodic orbit of $P$ ($P(a_{i})=a_{i+1}$) we have \[a_{2}-a_{1}\mid a_{3}-a_{2}\mid \ldots\mid a_{1}-a_{k}\mid a_{2}-a_{1}\] Can you explain me this, please?

It follows from the well-known lemma that, for all integers $a, b$ ($a \neq b$), $a-b | P(a)-P(b)$.

O, thank you

ychjae wrote: then $P(P(t))=t$ iff $P(t)\in S$ huh? why?

Soarer wrote: ychjae wrote: then $P(P(t))=t$ iff $P(t)\in S$ huh? why? Sorry, I make a very big mistake here .

My question: does this problem still hold over the reals? When I first saw it, I intuitively thought that the maximum possible cycle should be 2, because if you consider the graph of an arbitrary polynomial $f(x)$ of degree greater than 1, and the line $y = x$, then while you're iterating you're basically jumping from points on the function, to the line $y = x$, then back to the function, etc. So you're going around in a rectangular motion, and you either start diverging, start converging, or in the special case of an iteration of length 2, you create a perfect rectangle ($P(a) = b, P(b) = a$). Oh yeah and there's the case $P(a) = a$ as well, of course. Since we are given a positive integer $k$, and the convergence case would require infinitely many iterations, my first instinct is that the problem still holds over real polynomials with real coefficients. EDIT: Courtesy of Thomas Mildorf and Mathematica I see that it does not hold over all reals. Just pounding out the resulting polynomials from applying $P(P(x))$ for instance will give many distinct roots....

Maybe we should exploit the fact that $P$ divides iterations of $P$. In the easiest case, $P^{(2)}=QP$, where $P^{(k)}=PoPo \dots oP$ ($k>1$ times). Now $P^{(2)}(t)=t=Q(t)P(t) \Rightarrow P(t)$ divides $t$. But also $P(t)=Q(P(t))t$, and t divides $P(t)$, meaning $|P(t)|=|t|$. Now we have at most $2n$ such $t$. How do you finish it for this case ?

I feel slightly robbed by this question. For the case where the cycle length of $P(P\ldots P(x) \ldots ))$ is 3 or more, I quoted a famous problem out of from the USAMO in the 1970s, proved in Engel's Problem Solving. I got nothing for quoting it whereas I would have got 3 for proving it.

I also think some contestants got a serious advantage here. The problem from the USAMO is really famous, and it's also well known that any fixed point of $P \circ P \circ \cdots \circ P$ must be a fixed point of $P \circ P$.

is this solution right?please read it and tell me because if it is then again this problem is not hard at all.if it's wrong then if $k=1$ it is obvious.if $k=2$ let's say that there are $n+1$(if there are more it is even better) integers $x$ such that $P(P(x))=x$.let $a_{1}> a_{2}>... > a_{(}n+1 )$ be those $n+1$ integers.we clearly have$a_{i}-a_{(}i+1) \mid P(a_{i})-P(a_{(}i+1)) \mid P(P(a_{i}))-P(P(a_{(}i+1)))=a_{i}-a_{(}i+1)$so $| P(a_{i})-P(a_{(}i+1)) |=a_{i}-a_{(}i+1)$.adding this for all $i=1,2,...,n$ we get that $|P(a_{1})-P(a_{2})|+....+|P(a_{n})-P(a_{(}n+1))|=a_{1}-a_{(}n+1)= |P(a_{1})-P(_{(}n+1))|$. but$|P(a_{1})-P(a_{2})|+....+|P(a_{n})-P(a_{(}n+1))| \ge |P(a_{1})-P(_{(}n+1))|$.since in the last one we have equality then all $|P(a_{i})-P(_{(}i+1))|$have the same sign. 1)$P(a_{i})-P(_{(}i+1))>0$ =>$P(a_{i})-a_{i}=k$ for all $i=1,2,..,n+1$ =>$P(x)-x-k=0$ for n+1 numbers but this is a contradiction since P's degree is n 2)$P(a_{i})-P(a_{(}i+1))<0$=>$P(x)+x-k=0$ for n+1 numbers and again contradiction. if $k>2$ again we easily get in the same way that $| P(a_{i})-P(a_{i}+1) |=a_{i}-a_{i}+1$ and this is just case $k=2$ i can't find any mistakes.are there any?

well in Fact it is not a "hard" problem if you are used to polinomials! Obviouslyiy you have integeer coefficients you must use $a-b|p(a)-p(b)$ and later analitic properties: in this case analitic properties didnt help sou you only needed the divisibility and inequalities and some classical facts ( a polinomial of degree $n$ has $n$ roots) And finally the key idea was considering the numbers $p_{k+1}(x)-p_{k}(x)$ which was typical since their sum telescope to what we wanted! I didnt like about this problem some thinks, for example its ancestors http://www.kalva.demon.co.uk/usa/usa74.html However, It is not too bad if someone knewed that problem, it just told him there is no period of lenght 3, which I think many people thought whitout knowing it... Edit: I didnt read whats before my post...

indeed, the "ancestror" that pascual says is a very famous and wellknown usamo problem. in every olympiad training they teach it...

What you forgot to say is that the problem appeared in a kind of romanian TST some very long time ago for k=2. And believe me, this case is not much more difficult than this problem.

I think there is simpler solution. x-y | P(x)-P(y) But also P(x)-P(y) | Q(x)-Q(y) so, if Q(x)=x and Q(y)=y, x-y | P(x)-P(y) P(x)-P(y) | x-y. Then everything is clear.

that's what i did.but after $|P(a_{i})-P(a_{j})|=|a_{i}-a_{j}|$ it's not so clear and you must see that ineq in order to conclude about the sign.

It follows: If there are n+1 roots of Q(t) = t, a1 < a2 < a3 <... < a(n+1) then we must have : P(a1) < P(a2) <... < P(a(n+1)), or P(a1) > P(a2) > ... > P(a(n+1)), because if for some i<j<k P(a(i)), P(a(j)), P(a(k)) aren't sorted, we get contradiction. After this it's similar to another solutions. I think it's easier than author's solution, and problem isn't hard.

to nik:what's your argument for that contradiction? ps:indeed there are solutions much easier then the author's

First we reduce this to the case $k=2$. Claim. If $Q(x) = x$, then $P(P(x)) = x$. We utilize the fact that $$a-b \mid P(a)-P(b)$$for any integers $a, b$ and polynomial $P$ with integer coefficients. Construct the chain of divisibilities $$P(x) - x \mid P^2(x) - P(x) \mid \cdots \mid P^{n+1}(x) - P^n(x) = P(x) - x.$$This means that $$|P(x) - x| = |P^2(x) - P(x)| = \cdots = |x-P^{n-1}(x)|.$$Assume none of the terms are zero -- then, we are done. Observe their sum is 0, which means that there must exist at least one positive and negative term. Correspondingly, there must also exist a $k$ such that $$P^k(x) - P^{k-1}(x) = -(P^{k+1}(x) - P^k(x)).$$This means that $$P^{k+1}(x) = P^{k-1}(x).$$In turn, the terms of $P^i(x)$ are periodic with cycle 2, so $P(P(x)) = x$ as required. $\blacksquare$ Let $a, b$ be two distinct integers such that $P^2(a) = a$ and $P^2(b) = b$. We prove the following: either $P(x) = x$ for all $x$ with $P^2(x) = x$ ($\clubsuit$) or $P(x) + x = c$ is constant for all $x$ satisfying the condition. ($\diamondsuit$) We argue by contradiction. First, observe the two divisibility relations $$a-P(b) \mid P(a) - P^2(b) = P(a) - b,$$so $$|a-P(b)| = |P(a) - b|$$and $$a-b \mid P(a) - P(b) \mid a-b \iff |a-b| = |P(a) - P(b)|.$$There are four cases. $a-P(b) = P(a) - b$ and $a-b = P(a) - P(b)$. Then, $P(a) - a = b - P(b) = P(b) -b$, so $P(b) = b$ and $P(a) = a$. $a-P(b) = b-P(a)$ and $a-b = P(a) - P(b)$. Then, $a-b = P(b) - P(a) = b-a$, so $a=b$, contradiction. $a-P(b) = b-P(a)$ and $a-b = P(b) - P(a)$. Both assertions give us $a+P(a) = b + P(b)$, so $x+P(x)$ is constant for all necessary $x$. $a-P(b) = P(a) - b$ and $a-b = P(b) - P(a)$. The two assertions give $a-P(a) = b-P(b)$ and $a+P(a) = b+P(b)$, and adding yields $2a=2b$, contradiction. Assume for the sake of contradiction that there existed distinct $a, b$ such that $a$ satisfied $\clubsuit$ and $b$ satisfied $\diamondsuit$. Then the divisibility condition on $a, b$ implies $b$ must satisfy $\clubsuit$ as well, so the constant value $c = 2b$. But $a$ must satisfy $\diamondsuit$ as well, so $c=2a$, leading to a contradiction, as required. Since there are at most $n$ integers satisfying each condition, we are done.

Assume that there existed distinct $t_1 \leq t_2 \leq \ldots \leq t_{n+1}$ such that $P^k(t_i)=t_i$. Then, $ (t_i-t_j) \mid (P(t_i)-P(t_j)) \mid (P(P(t_i))-P(P(t_j))) \mid \ldots \mid P^k(t_i)-P^k(t_j)=(t_i-t_j)$, hence $|P(t_i)-P(t_j)|=t_i-t_j$ for all $i>j$. Note that $$t_n-t_1=|P(t_n)-P(t_1)| \leq |P(t_n)-P(t_{n-1})|+|P(t_{n-1})-P(t_{n-2})|+\ldots+|P(t_2)-P(t_1)|=(t_n-t_{n-1})+\ldots+(t_2-t_1)=t_n-t_1,$$hence we must have equality in the triangle inequality, so all $P(t_i)-P(t_{i+1})$ have the same sign. Suppose they are all positive, then $P(t_i)-P(t_j)=t_i-t_j$ for all $i>j$, hence $P(t_i)-t_i=P(t_j)-t_j=c$ for all $i,j$. Let $Q(x)=P(x)-x-c$. Then $Q$ has all $t_i$ as real roots, and as there are $n+1$ of them, $Q$ must be the zero polynomial, hence $P$ is linear, which contradicts the fact that $\deg P >1$.

Let $x,y$ be distinct roots of $Q.$ Notice $P^k(x)-P^k(y)=x-y\mid P(x)-P(y)$ and $P(x)-P(y)\mid P^2(x)-P^2(y)\mid\dots\mid P^k(x)-P^k(y)$ so $$x-y=|P(x)-P(y)|=|P^k(x)-P^k(y)|.\quad(*)$$Claim: $P$ is either increasing or decreasing over the integers. Proof. Notice $$|P(x+1)-P(x)+P(x+2)-P(x+1)|=2=|P(x+1)-P(x)|+|P(x+2)-P(x+1)|$$so $P(x+1)-P(x)$ and $P(x+2)-P(x+1)$ have the same sign. Induction finishes. $\blacksquare$ By $(*),$ $x-y=P(x)-P(y)$ for all root $x,y$ of $Q$ (or $x-y=P(y)-P(x),$ but assume $P(x)-P(y)$ is positive) so $P(x)-x=P(y)-y=\ell.$ We are done by considering $R(x)=P(x)-x-\ell,$ noting $n=\text{deg}(P)=\text{deg}(R)\ge\text{deg}(Q).$ $\square$

Suppose we have $P^k(a)=a$ and $P^k(b)=b$, so $P^k(a)-P^k(b)=a-b$. Since $x-y \mid p(x)-p(y)$ for all integer polynomials $p$, we have $$a-b \mid P(a)-P(b) \mid P^k(a)-P^k(b)=a-b,$$hence $|P(a)-P(b)|=|a-b|$. Not suppose $r_1>\ldots>r_m$ are the roots of $P^k(x)-x$, so we have $|P(r_i)-P(r_j)|=|r_i-r_j|$. I claim that $(r_i,P(r_i))$ are all collinear. Shift $P$ such that $P(r_1)=r_1$, and also WLOG $P(r_2)-P(r_1)=r_2-r_1$, so $P(r_2)=r_2$. Now, for any $i>2$, we have $P(r_i)-P(r_1)=P(r_i)-r_1=\pm(r_i-r_1) \implies P(r_i) \in \{r_i,2r_1-r_i\}$. Likewise, replacing $1$ with $2$ gives $P(r_i) \in \{r_i,2r_2-r_i\}$, hence $P(r_i)=r_i$ for all $i$. But if $m>n$, then $P$ is linear on at least $n+1$ points, which implies that $P$ itself is linear—contradiction. $\blacksquare$

Let $x$ be a value for which $Q(x)=x$. Note that \[x-P(x)\mid P(x)-P^2(x)\mid \dots \mid P^k(x)-P^{k+1}(x)=x-P(x)\]so $d=|P^i(x)-P^{i+1}(x)|$ is constant for $i=0,1,\dots,k-1$. Now, we'll show that if $Q(x)=x$ then either $P(x)=x$ or $P(P(x))=x$. Suppose otherwise, then $k\ge 3$. Without loss of generality, let $P(x)=x+d$. If $d=0$ we are done. If $P(P(x))=x$ we are done. If not, $P(P(x))=x+2d$. Thereafter, by discrete continuity there exists $i\ge 1$ such that $P^i(x)=x+d$ and $P^{i+1}(x)=x$. However, $P^{i+1}(x)=P(P^i(x))=P(x+d)=x+2d$, contradiction. It suffices to show that for at most $n$ integers does $P(x)=x$ or $P(P(x))=x$. Suppose $P(P(x_1))=x_1$ and $P(P(x_2))=x_2$, then $x_1-x_2\mid P(x_1)-P(x_2)\mid x_1-x_2$ so $|x_1-x_2|=|P(x_1)-P(x_2)|$. Similarly, $|x_1-P(x_2)|=|x_2-P(x_1)|$. Therefore, $x_1+P(x_1)=x_2+P(x_2)$. Thus, for all $x$ such that $Q(x)=x$, $x+P(x)$ is constant. Clearly, for any given constant $c=x+P(x)$ has at most $n$ roots. We are done.

It seems to me that the fact that $Q$ is an iterate of $P$ is unnecessary; we only need $Q = g \circ P$ for some non-constant polynomial $g$. The fact that we are working over integers is unnecessary; any integral domain whose group of units is $\{\pm 1\}$ works as well. I'll attempt a more general problem of interest. (In contrast, post #46 seems to be mainly interested in the cycles itself; just in case someone finds this post similar to #46...) Quote: Let $R$ be an integral domain such that its group of units, $R^{\times}$, is finite. Let $P \in R[X]$ be a polynomial of degree $n > 1$, and let $g \in R[X]$ be an arbitrary polynomial. Then $g \circ P$ has at most $\max\{n, |R^{\times}| + 1\}$ fixed points, and at most $n$ points if $|R^{\times}| = 2$, even when $n = 2$. I'll prove this when $|R^{\times}| = 2$ and when $R$ has positive characteristic. Further comments come after the attempted partial solution. Clearly, we can assume that $g$ is non-constant; else $g \circ P$ is constant and this only has one fixed point. By the theory of polynomials, for any $x, y \in R$, we have $x - y \mid P(x) - P(y) \mid g(P(x)) - g(P(y))$. In particular, since $R$ is an integral domain, if $x$ and $y$ are fixed points of $g \circ P$, then $P(x) - P(y)$ and $x - y$ are associates, i.e. $P(x) - P(y) = \alpha (x - y)$ for some $\alpha \in R$. Note that here, $\alpha$ may depend on $x$ and $y$, but the choice of $\alpha$ is unique if $x \neq y$. We will ignore $g$ from now on. Consider the complete graph $G = (V, E)$, where $V \subseteq R$ is the set of fixed points of $g \circ P$. Note that $V$ is finite since $\deg(g \circ P) = \deg(g) \deg(P) > 1$. Our goal is to show that $|V| \leq \max\{n, |R^{\times}| + 1, 25\}$. We colour each edges in $G$ with a unit of $R$; given $x, y \in V$ distinct, the edge $(x, y)$ is coloured $\alpha \in R^{\times}$ iff $P(x) - P(y) = \alpha(x - y)$. This is always possible due to the second previous paragraph. We claim that each triangle in $G$ uses exactly $1$ colour or $3$ colours. Indeed, fix a triangle in $G$, say with vertices $x, y, z$, and suppose that two of its edges have the same colour, say $(x, y)$ and $(x, z)$ with colour $\alpha \in R^{\times}$. Then $P(x) - P(y) = \alpha(x - y)$ and $P(x) - P(z) = \alpha(x - z)$... but then this forces $P(y) - P(z) = \alpha(y - z)$. So the third edge, $(y, z)$, also has colour $\alpha$, as desired. The above setup provides a quick solution when $|R^{\times}| = 2$. Indeed, in this case, we only have $2$ colours available, so every triangle in $G$ has to be monochromatic. Since $G$ is complete, this necessarily implies that $G$ is monochromatic, i.e. $P(x) - P(y) = \alpha(x - y)$ for all $x, y \in V$. In particular, there exists a constant $c \in R$ such that every element of $V$ is a root of the polynomial $P(X) - \alpha X - c$. This forces $|V| \leq n$ since $\deg(P) = n > 1$. The same holds as long as $G$ is monochromatic, even when $|R^{\times}| > 2$. On the other hand, consider the case where $R$ has characteristic $p > 0$, necessarily prime. The upper bound $|R^{\times}| + 1$ works here. To prove this, I'll start by proving a cute property that $R^{\times} \cup \{0\}$ is in fact a field contained in $R$.

For any triangle $(a, b, c)$ with $3$ colours, say with $(a, b)$ of colour $\gamma$, $(b, c)$ with colour $\alpha$, and $(c, a)$ of colour $\beta$, we obtain the equation $\gamma(a - b) + \alpha(b - c) + \beta(c - a) = 0$. In particular, solving for $c$ in terms of $a$, $b$, and the units $\alpha$, $\beta$, and $\gamma$ yields \[ (\gamma - \beta)(a - b) + (\alpha - \beta)(b - c) = 0 \iff c = b + \frac{\gamma - \beta}{\alpha - \beta} (a - b). \]If we write $a = b + r$, then $c = b + \delta r$, where $\delta = \dfrac{\gamma - \beta}{\alpha - \beta}$. But it is a unit by the above proof in this case. This sets up the solution for the positive characteristic case. Now fix a triangle $(a, b, c)$ with $3$ colours, and write $b = a + r$. As above, $c = a + \delta r$ for some unit $r$. Not only that, since $(a, b)$ and $(a, c)$ has distinct colour, for any $d \in V$ with $d \neq a, b, c$, the edge $(a, d)$ has distinct colour with at least one of $(a, b)$ or $(a, c)$. The previous paragraph yields that $d - a$ is a unit multiple of $r$ or $\delta r$; since $\delta$ is a unit, $d - a$ is a unit multiple of $r$ regardless. This means any vertices in the graph $G$ is either $a$ or can be written as $a + \alpha r$ for some unit $\alpha$. This proves that $|V| \leq |R^{\times}| + 1$. For characteristic zero case, one can show that $|R^{\times}| \leq 6$, and $R$ contains $\mathbb{Z}[i]$ if $|R^{\times}| = 4$, or $\mathbb{Z}[\omega]$ if $|R^{\times}| = 6$, where $\omega = \dfrac{1 + \sqrt{-3}}{2}$. In the former case with $G$ non-monochromatic, I got $|V| \leq 5$ by direct bashing. In the latter case, I got $|V| \leq 25$ using pure graph theory. But $25$ seems far from the best... would $|V| \leq 7$ be possible?

Clearly the claim hold for $k=1$ as $P(x)-x$ has at most $\deg(P)$ number of real zeors. Now suppose $k$ is the minimal integer such that $P^{k}(t)=t$. $\textcolor{red}{\mathrm{Claim:-}}$ either $k=1$ or $k=2$. $\textcolor{blue}{\mathrm{Pf:}}$ for $k=1$ it's shown , define $a_{n+1}=P(a_{n})$ for $n \geqslant 0$ , where $a_{0}=x$ and $P(a_{k})=a_{0}$ , now define $d_{i}=a_{i+1}-a_{i}$ Now since $P(x) \in \mathbb{Z}[x]$ , we have $a_{i+1}-a_{i}|P(a_{i+1})-P(a_{i}) =a_{i+2}-a_{i+1}=d_{i+1}$ so we have $d_{i}|d_{i+1}$ $\forall$ $0 \leqslant i \leqslant k$ now we also have $a_{k+1}=x$ , so $a_{k+1}=a_{0}$ , and $a_{k+2}=a_{1}$ , hence we have $d_{k+1}=d_{0}$ hence we have $|d_{0}|=|d_{1}|=|d_{2}|=\cdots =|d_{i}|=\Omega$ for $0 \leqslant i \leqslant k+1$ Now: if $\Omega=0$ so we have all $a_{i}'s$ to be equal , giving us $k \geqslant 3$ is not possible. if $\Omega \neq 0$ so we have that the set $\{ a_{1} , a_{2} , \cdots , a_{k+1}\} \subseteq \mathbb{Z}^{+}_{0}$ , hence by well ordering principle this set has a minimum. say $a_{\ell}$ , so $a_{\ell-1}>a_{\ell}$ , $a_{\ell+1}>a_{\ell}$ , so we have $d_{\ell-1}=-d_{\ell} \implies a_{\ell-1}=a_{\ell+1}$ , now we can take $P$ over until we get $a_{2}=a_{0}=x$ , or if not then we have $P(a_{\ell-2})=P(a_{\ell})\implies a_{\ell-2}=a_{\ell}$ so we do this until we get $a_{2}=a_{0}$ Hence in either case we have $k=2$ or $k=1$. So claim follows $\square$. Now: $\textcolor{red}{\mathrm{Claim:}}$ $P(P(x))=x$ has at most $\deg(P)$ number of integer solutions. $\textcolor{blue}{\mathrm{Pf:}}$ FTSOC assume that $P(P(x))=x$ has more than $\deg(P)$ number of solutions, suppose the solution set is represented by $\mathcal{S}:=\{x_{1}, x_{2} , \cdots x_{\deg(P)+m}\}$ for $m \in \mathbb{Z}^{+}$ , then we have $x_{1}-x|P(x_{1})-P(x)|P(P(x_{1}))-P(P(x))=x_{1}-x \implies P(x_{1})-P(x)=|x_{1}-x|$ for each $x \in \mathcal{S}$, so we get the polynomial equation $P(x)-x+c=0$ for some constant $c$ has more roots than it's degree which is a contradiction, hence the claim follows. $\square$ and hence there are at most $n$ integers $t$ such that $Q(t)=t.$

$\color{red}\textbf{Claim:-}$ We have to prove there are at most $n$ integers $t$ such that $Q(t)=t.$ $\color{blue}\textbf{Proof:-}$ We have $P(x)$ is an integer polynomial with degree $n > 1.$ And satisfies $Q(x)$ is a polynomial satisfies $$Q(x)=P(\underbrace{P(....(P(x)....))}_{\textbf{k times.}}\implies \boxed{Q(x)=P^{k}(x).}$$For proving this we use two lemmas. $$\textbf{Lemma-1:-} P^k(x)=x\implies P^2(x)=x.$$and $\textbf{Lemma -2:-}$ If $a$ and $b$ are two distinct integers and let $P(x)$ is a polynomial with integer coefficients then it satisfies $$a-b|P(a)-P(b).$$Assume for contradiction. Let's say $Q(t)=t$ has at least $n+1$ integer solutions. Now $\forall x$ $Q(t)=t\implies P(x)=x.$ The number of integer solution is at most $n$ Now Let's assume for every integer $y$ it follows that $Q(t)=t$ but $P(x) \ne x.$ But this satisfies $P^2(x)=x$ by first Lemma. We get from $$a-b|P(a)-P(b)\implies x-y|P(x)-P(y)|\underbrace{P(P(x)-P(P(y))}_{=x-y}$$Therefore we get, $$x-y|P(x)-P(y)|x-y$$Now from divisibility rule we get, $$|x-y| \le |P(x)-P(y)| \le |x-y|\implies \boxed{x-y=\pm P(x)\pm P(y).}$$Now From First equation we get, $$x-y=\underbrace{P(x)}_{=x}-P(y)\implies \boxed{y=P(y).} \implies\textbf{contradiction.}$$Now from second equation we get, $$x-y=-P(x)+P(y)\implies x+P(x)=y+P(y).$$Now we have $$P^k(x)=x\implies P^2(x)=x\implies x+P(x)=y+P(y).$$Let's assume $y$ is a constant $c$ we get, $x+P(x)=c$ has integer solution. Therefore from this we also get, $$x+P(x)=c\implies Q(x)=x.$$

Consider $P^k\left(x\right)=x$ and $P^k\left(y\right)=y$ It is obvious that $\left|P\left(x\right)-P\left(y\right)\right|=\left|x-y\right|$ So for any $t\in\mathbb{N}$,$P^t\left(x\right)-P^t\left(y\right)\mid P\left[P^t\left(x\right)\right]-P\left[P^t\left(y\right)\right]$ Then we get $P\left(x\right)-P\left(y\right)\mid x-y$ $\left|P\left(x\right)-P\left(y\right)\right|=\left|x-y\right|$ Now consider $a_1<a_2<\ldots<a_d$,$P^k\left(a_i\right)=a_i$ $\left|P\left(a_{i+2}\right)-P\left(a_{i+1}\right)\right|+\left|P\left(a_{i+1}\right)-P\left(a_i\right)\right|=a_{i+2}-a_i=\left|P\left(a_{i+2}\right)-P\left(a_i\right)\right|=\left|P\left(a_{i+2}\right)-P\left(a_{i+1}\right)+P\left(a_{i+1}\right)-P\left(a_i\right)\right|$ $P\left(a_{i+1}\right)-P\left(a_i\right)$ and $P\left(a_{i+2}\right)-P\left(a_{i+1}\right)$ have the same symbol So $P\left(a_i\right)$ is monotony,Let it be monotonously incremental $\left|P\left(a_{i+1}\right)-P\left(a_i\right)\right|=a_{i+1}-a_i$ $P\left(a_i\right)-a_i=C$ $P\left(x\right)-x-C$ The number of times is k So d is smaller than k Certification

Suppose that $Q$ had more than $n$ integer fixed points. In particular, $Q$ has at least $3$ integer fixed points. Claim: For any two different roots $a,b$ of $Q$, we have $P(a) - a = P(b) - b$ or $P(a) + a = P(b) + b$. Proof: Note that\[a - b \mid P(a) - P(b) \mid P^2(a) - P^2(b) \mid \cdots \mid Q(a) - Q(b) = a - b,\]so all the numbers in this chain of divisibilities have the same absolute value as $a - b$. Hence $a - b = P(a) - P(b)$ or $a - b = P(b) - P(a)$, which implies the claim. $\square$ Now fix two different roots of $Q$ as $a$ and $b$. Let $r\in \{-1,1\}$ satisfy $P(a) + ra = P(b) + rb = C$. Claim: For any other root $c$ of $Q$, we also have $P(c) + rc = C$. Proof: Clearly $P(c) - rc$ cannot be equal to both $P(a) - ra$ and $P(b) - rb$. WLOG that $P(c) - rc \ne P(a) - ra$. Then $P(c) + rc = P(a) + ra = C$, as desired. $\square$ Then the polynomial $P(x) + rx - C$ has $n+1$ roots, which is absurd since its degree is $n$ and it is nonconstant.

OG, We prove this as follows: FSTOC, assume there are more than $n$ integral solutions for $Q(x) = x$ , let any $n+1$ of those be $a_1,a_2 \cdots a_{n+1}$, all these are distinct. Now, $a_i- a_j|P(a_i)-P(a_j) | Q(a_i)-Q(a_j)= a_i- a_j$ $\implies P(a_i)-P(a_j)=a_i- a_j $ or $a_j- a_i$ Claim: $P(a_i)-P(a_j)=a_i- a_j$ always for fixed $i$ and for all $j$ or $ P(a_i)-P(a_j)=a_j- a_i$ always for fixed $i$ and for all $j$. Proof: Assume the contrary so let for a fixed $i$ and two $j$ (namely $j_1$ and $j_2$)(since $n+1\geq3$, we can chose 3 such indices) $P(a_i)-P(a_{j_1})=a_i- a_{j_1}$ $ P(a_{j_2})-P(a_i)-=a_i- a_{j_2}$ $P(a_{j_1})-P(a_{j_2})=a_{j_1}- a_{j_2}$ or $a_{j_2}-a_{j_1}$ Adding the 3 equations we, get $a_i=a_{j_1}$ or $a_i=a_{j_2}$ (A contradiction as all $a_i$ are distinct) Thus, proved Thus, if $P(a_i)-P(a_j)=a_j- a_i$ always for fixed $i$ and for all $j$, then $P(a_i)+a_i=P(a_j)+a_j=C_i$ for a fixed $i$ and all $j$, Thus, set $i=1$ and $j=2 \cdots n+1$. $\implies$ The polynomial $F(x)=P(x)+x-C_1=0$ has $n+1$ integral solutions, a contradiction! as the degree of $F(x)$ is $n$. If $P(a_i)-P(a_j)=a_i- a_j$ always for fixed $i$ and for all $j$,then $P(a_i)-a_i=P(a_j)-a_j=B_i$ for a fixed $i$ and all $j$, Thus, set $i=1$ and $j=2 \cdots n+1$. Similarly, we get The polynomial $R(x)=P(x)-x-B_1=0$ has $n+1$ integral solutions, a contradiction! as the degree of $R(x)$ is $n$.

Suppose $P$ has a cycle of the form $P(a_1)=a_2,P(a_2)=a_3,\dots,P(a_j)=a_1$ with $a_i$ distinct Then $a_1-a_2\mid a_2-a_3\mid\dots\mid a_j-a_1\mid a_1-a_2$. Thus $|a_1-a_2|=\dots=|a_j-a_1|$ and it is easy to check that we must have $j\le 2$. Suppose $P(a)=b,P(b)=a,P(c)=d,P(d)=c$ for $c,d$ not necessarily distinct but $a\ne b$. Then $a-c\mid b-d\mid a-c$, so $a-c=\pm(b-d)$ and either $a+b=c+d$ or $a+d=b+c$. We also have $a-d\mid b-c\mid a-d$ so $a-d=\pm(b-c)$ and either $a+b=c+d$ or $a+c=b+d$. Now $a+c=b+d$ and $a+d=b+c$ imply $a-b=c-d=-(a-b)$, contradiction. Thus $a+b=c+d$, which equals some universal constant $m$ for this polynomial $P$. Now if $Q(x)=x$ then $x$ is part of a cycle of length $1$ or $2$. If all cycles are length $1$, then $P(x)-x$ is degree $n$ and has at most $n$ integer roots, so $Q(x)=x$ also has at most $n$ integer solutions. Otherwise, if there is a cycle of length $2$, then all such elements of a cycle are roots of $P(x)+x-m$, which is degree $n$ and has at most $n$ integer roots. Thus $Q(x)=x$ also has at most $n$ integer solutions.

Suppose there are $n+1$ fixed points in $Q$, let $Q(x)=P^k(x)$, suppose $Q(a_i)=a_i$ for $i\in \{1, 2, \dots, n+1\}$, we have that $a_i-a_j\mid p(a_i)-p(a_j)\mid \dots \mid p^{k-1}(a_i)-p^{k-1}(a_j)\mid a_i-a_j$, thus $p(a_i)-p(a_j)=\pm(a_i-a_j)$ for all $i, j$, now suppose we have that $p(a_i)-p(a_k)=a_k-a_i$ and $p(a_j)-p(a_k)=a_j-a_k$, we get that $p(a_i)-p(a_j)=a_i+a_j-2a_k$ which implies that $a_k=a_i$ or $a_k=a_j$ which is a contradicition. Thus we have that $p(a_i)=a_i+k$ for a fixed $k$ or $p(a_i)=k-a_i$ and in both cases lagrange interpolation implies its linear which is a contradiction.

Note that $a-b|P(a)-P(b).$ From this we can easily see that there is a maximum cycle length of $2.$ Consider the two cycles $a$ to $b$ and $x$ to $y.$ We have that $a-x|b-y|a-x,$ so $a-x=\pm(b-y)$ so either we have $a+b=x+y$ or $a+y=b+x.$ Similarly we have that either $a+b=x+y$ or $a+x=b+y.$ Therefore $a+b=c+d,$ so every cycle of length $2$ has the two numbers sum to some constant $k.$ \newline Now, suppose all cycles have period $1.$ Then the number is simply the number of solutions to $Q(x)-x,$ which is a maximum of $n.$ If there is a cycle of length $2,$ then all valid numbers satisfy $P(x)+x-k,$ which also has at most $n$ solutions$.\blacksquare$