Problem 2470

Let $\mathbb{Z}$ denote the set of integers. We define
$$S_P = \{t \mid t \in \mathbb{Z} \text{ and } P(t) = t\} \quad \text{and} \quad S_Q = \{t \mid t \in \mathbb{Z} \text{ and } Q(t) = t\}.$$
Clearly, $S_P$ is a subset of $S_Q$. Also note that there are at most $n$ elements in $S_P$. This is so because that $t \in S_P$ if and only if $t$ is a root of polynomial $P(x) - x = 0$ of degree $n$, which has at most $n$ roots. If $S_Q = S_P$, we have nothing to prove. We assume that $S_P$ is a proper subset of $S_Q$, and that $t \in S_Q$ but $t \notin S_P$.
Consider the sequence $\{t_i\}_{i=0}^{\infty}$ with $t_0 = t$, $t_{i+1} = P(t_i)$ for every nonnegative integer $i$. Since $t \in S_Q$, $t_k = Q(t_0) = Q(t) = t = t_0$.
Since the polynomial $a - b$ divides the polynomial $a^m - b^m$ (where $m$ is a nonnegative integer), it is not difficult to see that the polynomial $a - b$ divides the polynomial $P(a) - P(b)$, where $P(x)$ is a polynomial with integer coefficients. In our current problem, then, we can conclude that the integer sequence $\{t_i\}_{i=0}^{\infty}$ satisfies the following sequence of divisibility relations
$$(t_{i+1} - t_i) \mid (P(t_{i+1}) - P(t_i)) = t_{i+2} - t_{i+1}$$
for every nonnegative integer $i$. Since $t_{k+1} - t_k = t_1 - t_0 = P(t) - t \ne 0$, each term in the chain of differences
$t_1 - t_0, t_2 - t_1, \dots, t_k - t_{k-1}, t_{k+1} - t_k$
is a nonzero divisor of the next one, and since $t_{k+1} - t_k = t_1 - t_0$, all these differences have equal absolute values. Let $t_i = \max\{t_0, t_1, \dots, t_k\}$. Then $t_{i-1} - t_i = -(t_i - t_{i+1})$, or $t_{i-1} = t_{i+1}$. It is then not difficult to see that $t_{i+2} = t_i$ for every $i$; that is,
$$t_1 = P(t_0) \quad \text{and} \quad t_0 = P(t_1) \quad \text{or} \quad P(P(t_0)) = t_0.$$

Therefore,
$$S_Q = \{t \mid t \in \mathbb{Z} \text{ and } P(P(t)) = t\}.$$
Without loss of generality, we may assume that $t_0 < t_1$. If $s_0$ is another element in $S_Q$, let $s_1 = P(s_0)$. (It is possible that $s_0 \in S_P$; that is, $s_1 = s_0$.) We further assume without loss of generality that $s_0 < s_1$ and $t_0 < s_0$; that is, $t_0 < s_0 \le s_1$ and $t_0 < t_1$. Note that $s_1 - t_0$ divides $P(s_1) - P(t_0) = s_0 - t_1$. We must have $t_0 < s_0 < s_1 < t_1$. Note that $s_0 - t_1$ also divides $P(s_0) - P(t_1) = s_1 - t_0$, it follows that $s_0 - t_1 = -(s_1 - t_0)$; that is,
$$t_0 + t_1 = s_0 + s_1 = s_0 + P(s_0).$$
In other words, $s_0$ is a root of the polynomial $P(x) + x = t_0 + t_1$. Since $P(x) + x$ has degree $n$, there are at most $n$ (integer) roots (including $t_0$) of $P(x) + x$. Hence there are at most $n$ elements in $S_Q$, completing our proof.