Taiwan IMO Selection Camp

$P(x) = x$ or $P(x) = c$, where $c \in \{1, \dots, 9\}$

Suppose $P(x) = a_{d}x^{d} + \cdots + a_{1}x^{1} + a_{0}$. Consider $n = 9 \times 10^{k}$, where $k$ is a sufficiently large positive integer; note that $S(n) = 9 \Rightarrow P(S(n)) = P(9)$.

1. We first prove that all coefficients are nonnegative.
Suppose there exists $0 \le i < d$ such that $a_i < 0$, then it is easy to see that the digits of $P(n)$ corresponding to $10^{ik+m+1}$ through $10^{(i+1)k-1}$ are all 9, so $S(P(n)) \ge 9(k-m-1)$. Taking $k$ sufficiently large, then $9(k-m-1) > P(9) = P(S(n))$, so $S(P(n)) \ne P(S(n))$, a contradiction.

2. Next we prove that $\deg(P(x)) \le 1$.
Since all coefficients are nonnegative, when $k$ is sufficiently large, $P(n)$ will consist of $a_d \times 9^d, a_{d-1} \times 9^{d-1}, \dots, a_0$ with some 0's inserted in between, that is,
$$S(P(n)) = S(a_d \times 9^d) + \cdots + S(a_0).$$
Also $S(P(n)) = P(S(n)) = P(9)$, so we have
$$S(a_d \times 9^d) + \cdots + S(a_0) = P(9) = a_d \times 9^d + \cdots + a_0. \quad (1)$$
However, for all positive integers $m$, it is clear that $S(m) \le m$, with equality holding only when $m \in \{1, \dots, 9\}$, so $\forall i \ge 2, a_i = 0$.

3. (1) also tells us that $a_1 \le 1$ and $a_0 \le 9$.
- If $a_1 = 1$ and $a_0 \ge 1$, take $n = 10^k + (10 - a_0)$, we get
$$S(P(n)) = S(10^k + 10) = 2 \neq 11 = P(11 - a_0) = P(S(n)).$$
So $P(x) = x$, substituting confirms it works.
- If $a_1 = 0$, then it is easy to see that $a_0 \in \{1, \dots, 9\}$ all satisfy the requirements of the problem.