设 $P(x)$ 为 $n$ 次（$n>1$）整系数多项式，$k$ 是一个正整数．考虑多项式 $Q(x)=P(P(\ldots P(P(x))\ldots))$，其中 $P$ 出现 $k$ 次．证明：最多存在 $n$ 个整数 $t$，使得 $Q(t)=t$．（罗马尼亚）
【难度】
【出处】
2006年第47届IMO试题
【标注】
【答案】
略
【解析】
首先，如果 $Q$ 的每个整数不动点也是 $P$ 的不动点，那么，结论成立．
对任意整数 $x_0$，满足 $Q(x_0)=x_0$，但 $P(x_0)\ne x_0$．我们定义 $x_{i+1}=P(x_i),i=0,1,2,\cdots$；则 $x_k=x_0$．
显然，对不同的 $u,v$，有 $u-v|P(u)-P(v)$，从而，对于下面（非零）差式，前一项能整除后一项．
$x_0-x_1,x_1-x_2,\cdots,x_{k-1}-x_k,x_k-x_{k+1}$
由于 $x_k-x_{k+1}=x_0-x_1$，所以所有的差式的绝对值相等．考虑 $x_m=\min(x_1,\cdots,x_k)$
则 $x_{m-1}-x_m=-(x_m-x_{m+1})$
于是 $x_{m-1}=x_{m+1}(\ne x_m)$，推出相继的差有相反的符号，我们得到 $x_0,x_1,\cdots$ 取两个不同的值，换句话说，$Q$ 的整数不动点为多项式 $P(P(x))$ 的不动点，我们将证明这样的不动点最多有 $n$ 个．
假设 $a$ 为满足性质的一个不动点，设 $b=P(a)\ne a$（我们已经假定这样的 $a$ 存在），那么 $a=P(b)$．取 $P(P(x))$ 的任意整数不动点 $\alpha$，令 $P(\alpha)=\beta$，则 $\alpha=P(\beta)$，$\alpha$ 和 $\beta$ 可以相同（即 $\alpha$ 可以是 $P$ 的不动点），但 $\alpha,\beta$ 与 $a,b$ 互不相同．对四对数 $(\alpha,a),(\beta,b),(a,b),(\beta,a)$ 应用前面的性质，得到 $\alpha-a$ 与 $\beta-b$ 相互整除，$a-b$ 与 $\beta-\alpha$ 相互整除，从而，
$a-b=\pm(\beta-\alpha),\alpha-a=\pm(\beta-b)$
如果在两式中取加号，则 $a-b=\beta-\alpha$ 与 $\alpha-a=\beta-b$，得到 $a-b=b-a$，与 $a\ne b$ 矛盾．那么至少有一个等式取负号，得到 $\alpha+\beta=a+b$，即 $a+b-\alpha-P(\alpha)=0$．
用 $C$ 表示 $a+b$ 的集合，我们已经证明 $Q$ 的每个不等于 $a$ 和 $b$ 的整数不动点都是多项式 $F(x)=C-x-P(x)$ 的根，对于 $a$ 和 $b$ 同样成立．由于多项式 $F(x)$ 与 $P(x)$ 有相同的次，即为 $n$ 次多项式，从而至多有 $n$ 个不同的整数根．证毕．
对任意整数 $x_0$，满足 $Q(x_0)=x_0$，但 $P(x_0)\ne x_0$．我们定义 $x_{i+1}=P(x_i),i=0,1,2,\cdots$；则 $x_k=x_0$．
显然，对不同的 $u,v$，有 $u-v|P(u)-P(v)$，从而，对于下面（非零）差式，前一项能整除后一项．
$x_0-x_1,x_1-x_2,\cdots,x_{k-1}-x_k,x_k-x_{k+1}$
由于 $x_k-x_{k+1}=x_0-x_1$，所以所有的差式的绝对值相等．考虑 $x_m=\min(x_1,\cdots,x_k)$
则 $x_{m-1}-x_m=-(x_m-x_{m+1})$
于是 $x_{m-1}=x_{m+1}(\ne x_m)$，推出相继的差有相反的符号，我们得到 $x_0,x_1,\cdots$ 取两个不同的值，换句话说，$Q$ 的整数不动点为多项式 $P(P(x))$ 的不动点，我们将证明这样的不动点最多有 $n$ 个．
假设 $a$ 为满足性质的一个不动点，设 $b=P(a)\ne a$（我们已经假定这样的 $a$ 存在），那么 $a=P(b)$．取 $P(P(x))$ 的任意整数不动点 $\alpha$，令 $P(\alpha)=\beta$，则 $\alpha=P(\beta)$，$\alpha$ 和 $\beta$ 可以相同（即 $\alpha$ 可以是 $P$ 的不动点），但 $\alpha,\beta$ 与 $a,b$ 互不相同．对四对数 $(\alpha,a),(\beta,b),(a,b),(\beta,a)$ 应用前面的性质，得到 $\alpha-a$ 与 $\beta-b$ 相互整除，$a-b$ 与 $\beta-\alpha$ 相互整除，从而，
$a-b=\pm(\beta-\alpha),\alpha-a=\pm(\beta-b)$
如果在两式中取加号，则 $a-b=\beta-\alpha$ 与 $\alpha-a=\beta-b$，得到 $a-b=b-a$，与 $a\ne b$ 矛盾．那么至少有一个等式取负号，得到 $\alpha+\beta=a+b$，即 $a+b-\alpha-P(\alpha)=0$．
用 $C$ 表示 $a+b$ 的集合，我们已经证明 $Q$ 的每个不等于 $a$ 和 $b$ 的整数不动点都是多项式 $F(x)=C-x-P(x)$ 的根，对于 $a$ 和 $b$ 同样成立．由于多项式 $F(x)$ 与 $P(x)$ 有相同的次，即为 $n$ 次多项式，从而至多有 $n$ 个不同的整数根．证毕．
答案
解析
备注
