IMO 2006 · Problem 5

Let \(P(x)\) be a polynomial of degree \(n>1\) with integer coefficients and let \(k\) be a positive integer. Consider the polynomial \(Q(x)=P(P(\ldots P(P(x))\ldots))\), where \(P\) occurs \(k\) times. Prove that there are at most \(n\) integers \(t\) such that \(Q(t)=t\).

Official text of the problem. Official problem paper (PDF)

Solution

Write \(P^{\circ j}\) for the \(j\)-fold composition of \(P\), with \(P^{\circ 0}(x)=x\), and let \[ S=\{t\in\mathbb Z:P^{\circ k}(t)=t\}. \] Since \(P^{\circ k}(x)-x\) has degree \(n^k\), the set \(S\) is finite. Moreover, \(P\) maps \(S\) into itself, because for \(t\in S\), \[ P^{\circ k}(P(t))=P(P^{\circ k}(t))=P(t). \]

We first show that \(P\) preserves distances between elements of \(S\). For any integers \(u,v\), the fact that \(P\) has integer coefficients gives \[ u-v\mid P(u)-P(v), \] by factoring each difference \(u^j-v^j\).

Now take distinct \(u,v\in S\), and put \[ d_i=P^{\circ i}(u)-P^{\circ i}(v) \qquad(0\le i\le k). \] Every \(d_i\) is nonzero: otherwise, applying \(P^{\circ(k-i)}\) would give \(u=v\). Also, \(d_i\mid d_{i+1}\) for \(0\le i<k\), while \(d_k=d_0\). Consequently, \[ |d_0|\le |d_1|\le\cdots\le |d_k|=|d_0|, \] so all these inequalities are equalities. In particular, \[ |P(u)-P(v)|=|u-v|. \tag{1} \]

If \(S\) has at most one element, the desired bound is immediate. Otherwise, let \[ a=\min S,\qquad b=\max S, \] so \(a<b\). Since \(P(a),P(b)\in S\), equation (1) implies \[ |P(a)-P(b)|=b-a. \] The only two points of \([a,b]\) at this distance are its endpoints. Thus either \(P(a)=a\) or \(P(a)=b\).

  • If \(P(a)=a\), then for every \(t\in S\), equation (1) (also trivially valid when \(t=a\)) gives \[ P(t)-a=|P(t)-a|=|t-a|=t-a, \] because \(P(t),t\in[a,b]\). Hence \(P(t)=t\), so every element of \(S\) is a root of \(P(x)-x\).

  • If \(P(a)=b\), then for every \(t\in S\), \[ b-P(t)=|P(t)-b|=|t-a|=t-a. \] Hence \(P(t)=a+b-t\), so every element of \(S\) is a root of \(P(x)+x-(a+b)\).

Both polynomials have degree \(n\), since \(n>1\). A nonzero polynomial of degree \(n\) has at most \(n\) distinct roots, so in either case \(|S|\le n\), as required. \(\square\)

The solution was checked against the official IMO shortlist solutions.