Estonia — Open Contests

a) Take $P(x) = -x$ and $c = 1$, then $P(c) = -1 \neq c$ and $P(P(c)) = P(-1) = 1 = c$.

b) Suppose that there exist a polynomial with integer coefficients $P(x)$ and an integer $c$, for which $P(c) \neq c$, $P(P(c)) \neq c$ and $P(P(P(c))) = c$. Notice that $P(c) \neq P(P(c))$, because otherwise $P(P(c)) = P(P(P(c))) = c$, which would contradict the assumption.
In the following calculations we will use the well-known property of polynomials with integer coefficients: $k - m \mid P(k) - P(m)$ for any distinct integers $k$ and $m$.
Using this and the premise that $P(P(P(c))) = c$, we see that number $c - P(c) = P(P(P(c))) - P(P(P(P(c))))$ is divisible by $P(P(c)) - P(P(P(c))) = P(P(c)) - c$, which in turn is divisible by $P(c) - P(P(c))$, which in turn is divisible by $c - P(c)$. Hence $|c - P(c)| \ge |P(P(c)) - c| \ge |c - P(c)|$, implying $|c - P(c)| = |P(P(c)) - c|$, and similarly $|c - P(c)| = |P(c) - P(P(c))|$.
Therefore three numbers $c$, $P(c)$ and $P(P(c))$ are all at the same distance away from each other on the number line, which is possible only when those numbers coincide, that is $c = P(c) = P(P(c))$, which contradicts the assumptions made. This contradiction shows that polynomial $P(x)$ and integer $c$ do not exist.