IMO 2006 Shortlisted Problems

The claim is obvious if every integer fixed point of $Q$ is a fixed point of $P$ itself. For the sequel assume that this is not the case. Take any integer $x_0$ such that $Q\left(x_0\right)=x_0$, $P\left(x_0\right)\ne x_0$ and define inductively $x_{i+1}=P\left(x_i\right)$ for $i=0,1,2,\dots$; then $x_k=x_0$. It is evident that $$\begin{array}{c}P(u)-P(v)\text{ is divisible by }u-v\text{ for distinct integers }u,v\text{. }\end{array}\text{\hspace{1em}(1)}$$ (Indeed, if $P(x)=\sum a_i{x}^i$ then each $a_i\left(u^i-v^i\right)$ is divisible by $u-v$.) Therefore each term in the chain of (nonzero) differences $$\begin{array}{c}{x}_0-x_1,x_1-x_2,\dots ,x_{k-1}-x_k,x_k-x_{k+1}\end{array}\text{\hspace{1em}(2)}$$ is a divisor of the next one; and since $x_k-x_{k+1}=x_0-x_1$, all these differences have equal absolute values. For $x_m=\min \left(x_1,\dots ,x_k\right)$ this means that $x_{m-1}-x_m=-\left(x_m-x_{m+1}\right)$. Thus $x_{m-1}=x_{m+1}\left(\ne x_m\right)$. It follows that consecutive differences in the sequence (2) have opposite signs. Consequently, $x_0,x_1,x_2,\dots$ is an alternating sequence of two distinct values. In other words, every integer fixed point of $Q$ is a fixed point of the polynomial $P(P(x))$. Our task is to prove that there are at most $n$ such points. Let $a$ be one of them so that $b=P(a)\ne a$ (we have assumed that such an $a$ exists); then $a=P(b)$. Take any other integer fixed point $\alpha$ of $P(P(x))$ and let $P(\alpha )=\beta$, so that $P(\beta )=\alpha$; the numbers $\alpha$ and $\beta$ need not be distinct ( $\alpha$ can be a fixed point of $P$ ), but each of $\alpha ,\beta$ is different from each of $a,b$. Applying property (1) to the four pairs of integers ( $\alpha ,a$ ), ( $\beta ,b$ ), $(\alpha ,b),(\beta ,a)$ we get that the numbers $\alpha -a$ and $\beta -b$ divide each other, and also $\alpha -b$ and $\beta -a$ divide each other. Consequently $$\begin{array}{c}\alpha -b=\pm (\beta -a),\alpha -a=\pm (\beta -b).\end{array}\text{\hspace{1em}(3)}$$ Suppose we have a plus in both instances: $\alpha -b=\beta -a$ and $\alpha -a=\beta -b$. Subtraction yields $a-b=b-a$, a contradiction, as $a\ne b$. Therefore at least one equality in (3) holds with a minus sign. For each of them this means that $\alpha +\beta =a+b$; equivalently $a+b-\alpha -P(\alpha )=0$. Denote $a+b$ by $C$. We have shown that every integer fixed point of $Q$ other that $a$ and $b$ is a root of the polynomial $F(x)=C-x-P(x)$. This is of course true for $a$ and $b$ as well. And since $P$ has degree $n>1$, the polynomial $F$ has the same degree, so it cannot have more than $n$ roots. Hence the result.