Problem: Suppose that $P(x)$ is a polynomial with degree at least $2$ and integer coefficients. Let $Q(x)$ have the form $$ Q(x) = P(P(P(\cdots P(x) \cdots))) $$ for some finite number of nested $P$s. Prove that the equation $Q(t)=t$ can have at most $ \text {deg}(P) $ integer solutions.
Thoughts: Graphing it doesn't help as the key to this problem is the integer restriction. Taking inverses don't help as they are ugly to deal with. Induction, maybe? But how?
Any thoughts would be greatly appreciated!
This is IMO 2006 Problem 5
A solution to it is this:
Suppose $a$ is a solution to $Q(x) = x$. Let $a_0 = a$ and $P^m(a) = a_m$. Then we know $(a_z - a_{z-1})|(a_{z+1}-a_z)$ for all $z \ge 1$. In particular, $(a_k - a_{k-1})|(a_1 - a_0)$ so we quickly deduce that $P$ has order $2$ on $a$ or order $1$. This is because firstly we have $$\prod_{i=1}^k \frac{a_{i+1} - a_{i}}{a_{i} - a_{i-1}} = 1 \implies \frac{a_{i+1} - a_{i}}{a_{i} - a_{i-1}} = \pm 1$$ Now suppose $m$ is the minimum number of $P$'s you need to apply on $a$ to reach $a$ again where $m > 1$. Then the $a_i$ are distinct. One quickly deduces if one of them were $-1$, we would have $a_{i+1} = a_{i-1}$ which implies $m=2$. Thus we can assume all of them are equal to $1$, but then the $a_i$ form an arithmetic progression which is absurd. Thus it is only possible $m=1$ or $m=2$.
Now, $P(x) = x$ has at most $\deg P$ solutions. Thus if there does not exist an $a$ such that $P(P(a)) = a$ while $P(a) \neq a$, we are done. Now suppose $P(P(a)) = a$ and $P(a) = b$ and $P(c) = d, P(d) = c$. Then $(a-c)|(b-d)$ and $(b-d)|(a-c) \implies a-c = \pm (b-d)$. One also knows $(a-d)|(b-c)$ and $(b-c)|(a-d) \implies a-d = \pm(b-c)$. But then one quickly deduces $a+b = c+d$. Note that this implies if $P(z) = z$ then $2z = a+b$ by letting $c=d=z$. Now let $a$ be a solution to $P(P(a)) = a$. Then any $z$ such that $Q(z) = z$ is a root of $x + P(x) - a - P(a)$, which has at most $\deg P$ roots so we are done.