The answer is $P(x) = c$ where $c \in \{1, \dots, 9\}$ as well as $P(x) = x$. Obviously they work. First, note that $P$ is eventually nonnegative (by taking $S(n)$ large), so the leading coefficient of $P$ is positive. Thus let \[ P(x) = a_d x^d + \dots + a_0. \] Main idea: we now plug in \[ n = 9 \cdot 10^e \]where $e$ is sufficiently large (say, $e > |a_d| + \dots + |a_0| + 2016^{d+100}$). We obtain then that \[ \sum_k a_k 9^k = P(9) = S(P(n)). \]Now, if any of the $a_i$ is negative, then $P(n)$ will have a string of at least $e - O(1)$ $9$'s in its decimal representation, contradiction. So all $a_i$ are nonnegative. For $e$ large enough the decimal representation of $P(n)$ then consists of the decimal representation of each $a_k 9^k$, separated by several zeros. In other words we have that \[ \sum_k a_k 9^k = \sum_k S(a_k 9^k). \]However, we know $m \ge S(m)$ for each positive integer $m$, with equality if and only if $m \in \{0, 1, 2, \dots, 9\}$. Thus $a_k 9^k \in \{0, 1, \dots, 9\}$ for every $k$. This implies that $a_0 \in \{0, \dots, 9\}$, $a_1 \in \{0,1\}$ and $a_k = 0$ for $k \ge 2$. From here we recover the solution set from before.

My solution $S(P(n)) = P(S(n))$ . Plug in $n = 10^k-1$ then $P(9k) = S(P(10^k-1)) \leq 9 (log (P(10^k-1))+1)$ Let $P(x) = a_rx^r+...+a_0$ then $P(n) < a_rn^{r+1}$ for $n$ big enough . Then $9(log (P(10^k-1))+1) < 9(log(a_r(10^k-1)^{r+1})+1) < 9((r+1)log(10^k)+1+log(a_r)) = 9((r+1)k+1+log(a_r))$ So $P(9k) < 9(k(r+1)+1+log(a_r))$ for all $k $. Then the degree of $P$ is atmost $1$ When $deg$ $P = 1$. Let $P(x) = ax+b$ . Then $S(an+b) = aS(n)+b \implies S(a.10^k+b) = S(a)+S(b) = a+b$ . Then , $a,b$ has only 1 digit . Also , $a+S(a+b)=S(a)+S(a+b)=S(a.(10^k+1) +b)=2a +b \implies S(a+b) = a+b$ $a+S(2a+b)=S(a(10^k+2)+b)3a+b \implies S(2a+b) = 2a+b$ . Similary we have $S(9a+b) = 9a+b$ . Then , $a = 1 , b = 0$ Then , $P(x) = x$. If $P$ is constant then $P \equiv c$ with $c$ has only one digit

Answer. $P(x)$ is either a constant $1, \dots, 9$, or $P(x) = x$. Let $P(x) = a_d x^d + a_{d - 1} x^{d - 1} + \dots + a_0$. Set $n = 10^k$ for $k$ large. Then, $S(P(10^k)) = P(1)$: $S(P(10^k))$ is constant for $k$ large. This means that all coefficients of $P$ are nonnegative (otherwise, $P(10^k)$ would have long strings of nines, meaning $S(P(10^k))$ unbounded). Now consider $n = m 10^k$ for $k$ large. Then $S(P(m 10^k)) = P(S(m))$, or \[S(a_d m^d 10^{kd} + a_{d - 1} m^{d - 1} 10^{k(d - 1)} + \dots + a_0) = P(S(m))\]or, if $k$ is large enough, \begin{eqnarray*} S(a_d m^d) + S(a_{d - 1} m^{d - 1}) + \dots + S(a_0) & = & P(S(m))\\ & = & a_d S(m)^d + a_{d - 1} S(m)^{d - 1} + \dots + a_0. \end{eqnarray*}However, observe that for each $i$, \[S(a_i m^i) \le S(a_i) S(m)^i \le a_i S(m)^i.\]Summing the above inequality over $i = \{0, \dots, d\}$, observe that equality holds. Thus, we have equality: $S(a_i m^i) = a_i S(m)^i$ for all $i$ and $m$. Now, we classify $a$ and $i$ such that $S(a m^i) = a S(m)^i$ for all $m$. This equality holds iff the product $a \cdot \underbrace{m \cdots m}_{i}$ has no carries in base ten. Note that $m = 1$ gives $S(a) = a$, so $a \in \{0, \dots, 9\}$. If $a = 0$, the equality always holds, so assume $a \ge 1$. If $i = 0$, then the equality is $S(a) = a$, so $a \in \{1, \dots, 9\}$. If $i = 1$, then the equality is $S(am) = aS(m)$; if $a \ge 2$, then $m = 9$ gives a contradiction. If $a = 1$, the equality is true. If $i \ge 2$, then the equality is $S(a m^i) = a S(m)^i$, but selecting $m = 9$ will give carries, so the equality is not possible. Thus, we deduce that for $S(a m^i) = a S(m)^i$ to hold for every $m$, either $a = 0$, or $(a, i) = (1, 0), \dots, (9, 0), (1, 1)$. It follows that $P(x) = 1, \dots, 9$, or $P(x) = x, x + 1, \dots, x + 9$. It is clear that the constant polynomials $1, \dots, 9$ and $P(x) = x$ work. Now suppose $P(x) = x + c$, with $c \in \{1, \dots, 9\}$: we have \[S(n + c) = S(n) + c\]for all $n \ge 2016$, which is obviously false. The solutions are constants $P \in \{1, \dots, 9\}$ and $P(x) = x$.

I have this problem solved except in the case that $P$ is linear, someone please give me a hint (only a hint, I do not want the problem spoiled for me) on how to proceed if $P$ is linear?

Can someone check if this works? I claim that the only solutions are $P(x)=x$ and $P(x) = k$ where $\{0 \le k \le 9 \mid k \in \mathbb{N}\}$. Clearly these solutions all work. Let $P(x) = a_0 + a_1 x+a_2x^2 + a_3 x^3 + \cdots + a_t x^t$. Now take $n = 9 \cdot 10^k$ where $k$ is greater than the number digits of $\max(a_0, 9a_1, \cdots, 9^ta_t)$. Then notice that $P(S(n)) = a_0 + 9a_1 + \cdots + 9^t a_t$ so \begin{align*} a_0 + 9a_1+81a_2 + \cdots + 9^t a_t &= S(P(n)) \\ &= S(a_0 + 9a_1 \cdot 10^k + \cdots + 9^ta_t \cdot 10^{10k}) \\ &= S(a_0) + S(9a_1) + \cdots + S(9^ta_t) \end{align*}Since $S(p) \le p$ for all integers $p$, we must have $a_i = 0$ for $2 \le i \le a_t$. Moreover, $0 \le a_0 \le 9$ and $0 \le a_1 \le 1$. It suffices to show that $P(n) = x+a_0$ where $1 \le a_0 \le 9$ does not work. Simply take $n = 2019$ so we have $12+a_0 = S(2019 + a_0)$. Checking, we see that there are no solutions for $1 \le a_0 \le 9$ so we are done. $\blacksquare$

Vfire wrote: Can someone check if this works? I claim that the only solutions are $P(x)=x$ and $P(x) = k$ where $\{0 \le k \le 9 \mid k \in \mathbb{N}\}$. Clearly these solutions all work. Let $P(x) = a_0 + a_1 x+a_2x^2 + a_3 x^3 + \cdots + a_t x^t$. Now take $n = 9 \cdot 10^k$ where $k$ is greater than the number digits of $\max(a_0, 9a_1, \cdots, 9^ta_t)$. Then notice that $P(S(n)) = a_0 + 9a_1 + \cdots + 9^t a_t$ so \begin{align*} a_0 + 9a_1+81a_2 + \cdots + 9^t a_t &= S(P(n)) \\ &= S(a_0 + 9a_1 \cdot 10^k + \cdots + 9^ta_t \cdot 10^{10k}) \\ &= S(a_0) + S(9a_1) + \cdots + S(9^ta_t) \end{align*}Since $S(p) \le p$ for all integers $p$, we must have $a_i = 0$ for $2 \le i \le a_t$. Moreover, $0 \le a_0 \le 9$ and $0 \le a_1 \le 1$. It suffices to show that $P(n) = x+a_0$ where $1 \le a_0 \le 9$ does not work. Simply take $n = 2019$ so we have $12+a_0 = S(2019 + a_0)$. Checking, we see that there are no solutions for $1 \le a_0 \le 9$ so we are done. $\blacksquare$

Plugging $n=10^k$ we get : $P(1)=S(P(10^k))$ which implies all the cofficients of $P$ are nonnegative We will use $S(a+b)\le S(a)+S(b)$ with equality when there is no carry in the addition $a+b$ Let $P(x) = a_d x^d + a_{d - 1} x^{d - 1} + \dots + a_0$ $S(P(x))=S(a_d x^d + a_{d - 1} x^{d - 1} + \dots + a_0)\le S(a_d x^d) + S(a_{d-1} x^{d-1}) + \dots + S(a_0)\\ \le a_dS(x^d) + a_{d-1}S(x^{d-1}) + \dots + a_0\le a_dS(x)^d + a_{d-1}S(x)^{d-1} + \dots + a_0=P(S(x))$ So we have : $S(x^i)=S(x)^i\implies$ ther is no carry in the addition : $\underbrace{x+x+\dots+x}_{x^{i-1}}$ Plugging $x=6666\implies i={0,1}$ Also we have : $S(a_ix^i)=a_iS(x^i)\implies$ ther is no carry in the addition : $\underbrace{x^i+x^i+\dots+x^i}_{a_i}$ Plugging $x=6666\implies a_i=\{0,1\}$ where $1 \le i\le d$ So either $P(x)=c$ easily we get $0 \le c\le 9$ is a solution Or $p(x)=x+c\implies S(n)+c=S(n+c)\implies c=0$

Let $P(x) = a_n x^n + \cdots + a_2 x^2 + a_1 x + a_0$. As $P(x)$ is positive, so $a_n$ (being the coefficient of the highest power of $x$) must be non-negative. Putting in $x = 10^k$, where $k > max(a_n, \dots, a_2, a_1, a_0)$ gives us: $S(P(10^k)) = P(S(10^k)) \Rightarrow S(a_n 10^{nk} + \cdots + a_2 10^{2k} + a_1 10^k + a_0) = P(1) = a_n + \cdots + a_2 + a_1 + a_0 \Rightarrow S(P(10^k))$ becomes constant for large k. If any of $a_i$, where $0 \le i \le n$ are negative, there will be a string of $9$s in the number, which will increase in length (and hence, the sum will also increase) as $k$ becomes larger, which is a contradiction. Therefore, all $a_i \ge 0$. Putting in $x = 9 \cdot 10^k$, where $k > max(9^n a_n, \dots, 81a_2, 9a_1, a_0)$ gives us: $S(9^n \cdot 10^{nk} a_n + \cdots + 81 \cdot 10^{2k} a_2 + 9 \cdot 10^{k} a_1 + a_0) = P(9) = 9^n a_n + \cdots 81 a_2 + 9 a_1 + a_0$ $\Rightarrow S(9^n a_n) + \cdots + S(81 a_2) + S(9 a_1) + S(a_0) = 9^n a_n + \cdots 81 a_2 + 9 a_1 + a_0$. Since we have $S(t) \le t$ with equality holding if and only if $t \in \{0, 1, 2, \dots, 9\}$, so all of $a_i = 0$, for $i \ge 2$, $a_1 \in \{0, 1\}$ and $a_0 \in \{0, 1, 2, \dots, 9\}$, otherwise the expressions above cannot be equal. Case 1: $P(x) = x + a_0 \Rightarrow S(x + a_0) = S(x) + a_0$, for $x \ge 2016$, which is obviously only true when $a_0 = 0$, leading us to the solution $P(x) = x$. Case 2: $P(x) = a_0$ which obviously works given the above conditions. So, $P(x) = x$ and $P(x) = c$ where $c \in \{0, 1, 2, \dots, 9\}$ are the only solutions.

Claim: $P(n) = n$ or $P(n) = t$ for any $t \in \{ 1, \ldots , 9 \}$ are the only solutions. Clearly, these solutions does work. $S(k) \leq k$, with equality occurring while $1 \leq k \leq 9$, which is obvious. Let $P(n) = \sum_{i}a_i n^i$. Chose arbitrary $k$ such that $10^k > \max(a_i)$, which is positive since leading coefficient is positive. $$S(P(10^k)) = P(S(10^k))$$$$S(\sum_{i}a_i (10^k)^i) = P(1) = \sum_{i}a_i$$First, see that each coefficient is non-negative, or else taking large $k$ will make there exists a large amount of $9$'s in its decimal representation and thus $P(1)$ arbitrarily large, contradiction. Then, notice that since $10^k > a_i$, there is no carry-over while taking the sum, so we have: $$S(\sum_{i}a_i (10^k)^i) = \sum_{i} S(a_i)$$Thus, we find that $\sum_{i} S(a_i) = \sum_{i}a_i$ which means that $a_i \in \{ 0, 1, \ldots , 9 \}$ Now, chose $t$ with $1 \leq t \leq 9$ and arbitrary $k$ such that $10^k > \max(a_i t^i)$. Then, $$S(\sum_{i}a_i (t \cdot 10^k)^i) = P(S(t \cdot 10^k)) = P(t) = \sum_{i}a_i t^i$$Likewise, we obtain: $$ \sum_{i} S(a_i t^i) = \sum_{i} a_i t^i$$This implies that $1 \leq a_i t^i \leq 9$ for any $t \mid 1 \leq t \leq 9$. It is trivial to see that the only possible $a_i t_i$ are $t=0$ or $t=1, a_i = 1$. So, we have $P(n) = an + t$ for any $t \in \{ 0, 1, \ldots , 9 \}$ and $a \in \{ 0, 1 \}$. We can easily verify that that out of the $20$ solutions in this form, only $P(n) = n$ or $P(n) = t$ for any $t \in \{ 1, \ldots , 9 \}$ works. So, these are the only solutions.

The answer is $P(x) = x$ for all $x$ or $P(x) = m$ for all $x$, for some $m \in \{1, 2, \dots , 9 \}$. If $P(x)$ is always a constant $m$, then we have $S(m) = m$, which easily implies that $m \in \{1, 2, \dots , 9\}$. Now assume that $\text{deg}(P) \geq 2$, and we will derive a contradiction. In the given equation take $n = 10^k-1$ for arbitrarily large $k$; then we get $S(P(10^k-1)) = P(9k)$. Note that $S(P(10^k-1)) \leq 9(\text{log}_{10} (P(10^k-1))+1)$. Thus we have $P(9k) \leq 9(\text{log}_{10} (P(10^k-1))+1) \Rightarrow 10^{\frac{P(9k)}{9}} \leq P(10^k-1)+1$. Let $\text{deg}(P) = d$. Note that for large enough $x$, we have $P(x)+1 < P(x+1) < x^{d+1}$. Thus we have $10^{\frac{P(9k)}{9}} < 10^{k(d+1)}$. But obviously $\frac{P(9k)}{9} > k(d+1)$ for large enough $k$, so we have $10^{\frac{P(9k)}{9}} > 10^{k(d+1)}$, contradiction. Now we do the case $\text{deg}(P) = 1$. Let $P(x) = ax+b$ for an integer $b$ and a positive integer $a$. We previously derived that $10^{\frac{P(9k)}{9}} \leq P(10^k-1)+1$ for large enough $k$; thus we have $10^{ak+\tfrac{b}{9}} \leq a (10^k-1)+b+1$. But if $a>1$ then the LHS is greater than the RHS for sufficiently large $k$. Thus $a=1$, and $P(x) = x+b$. But by the given we then have $S(x+b) = S(x)+b$; taking $x = 10^m$ for sufficiently large $m$, we have $S(b)+1 = b+1 \Rightarrow S(b) = b$, so $b \in \{0, 1, 2, \dots, 9 \}$. Taking $x = 109$ eliminates all positive values of $b$; thus we can only have $P(x) = x$, and we are done as claimed.

Nice and easy! Here's my solution: The case when $P$ is constant (say $P \equiv C$) gives $S(C)=C$, and so $1 \leq C \leq 9$ ($C \neq 0$ so as to make $P$ positive). From now on assume that the degree of $P$ is $d\geq 1$, and write $P(x)=\sum_{i=0}^d a_ix^i$ with $a_d>0$ (since $\lim_{x \mapsto \infty} P(x)=\infty$). Putting $n=10^k$ in the given equation (for $k>3$), we get $$a_0+a_1+ \dots +a_d=P(1)=P(S(10^k))=S(P(10^k))=S(a_0+10^ka_1+ \dots +10^{kd}a_d)$$By taking $k> \max_{0 \leq i \leq d} \lfloor \log(a_i) \rfloor$, we can get all $a_0,a_1, \dots ,a_d$ in different blocks when $P(10^k)$ is written. If any of the $a_i$'s is negative, then we will get arbitrarily long chains of $9$'s in $P(10^k)$, and so $S(P(10^k))$ will eventually exceed $P(1)$. So all $a_i$'s must be non-negative. In particular, this means that $P$ is strictly increasing for all $x>0$ (here we can say "strictly" since $a_d>0$). So for all sufficiently large $m$, there exists a unique $x_0>0$ such that $P(x_0)=10^m$. Applying the problem condition for $n=x_0$ then gives $P(S(x_0))=1$. But, $S(x_0) \geq 1$ implies that $P(S(x_0)) \geq P(1)$. Thus, we get $$0<a_0+a_1+ \dots +a_d \leq 1 \Rightarrow a_0=a_1= \dots =a_{d-1}=0 \text{ and } a_d=1$$Hence, $P(x)=x^d$, and so the problem condition translates to $S(n^d)=S(n)^d$. Putting $n=8000$ gives $S(8^d)=8^d$, and so we must have $d \leq 1$. Thus, the only solutions are $P=\text{id}$ and $P \equiv 1,2, \dots ,9$. $\blacksquare$

This was surprisingly easy... The answer is $P(x)=a$ where $a\in\{1,2,3,4,5,6,7,8,9\}$ or $P(x)=x$. Let us assume that $P(x)=\sum_{i=0}^m a_ix^i$ for integers $a_i$. Now if some $a_i$ are negative, then if we let $n=10^k$ for some sufficiently large $k$ (like $k>\max(a_1,a_2,\dots,a_m)$), then $S(P(10^k))=P(S(10^k))=P(1)$. But $P(1)=\sum_{i=0}^m a_i$ and $S(P(10^k))=\text{Sum of non-negative terms } a_i+\text{ other positive stuff } \neq P(1)=\text{Sum of non-negative terms } a_i+\text{ sum of negative terms } a_j$. Hence all $a_i$ are non-negative. Then choose $n=9\cdot 10^k$ for some suitably very large $k$ (specifically, $k>\max( a_i\cdot9^i)$ for $i=0,1,\dots,9$ would suffice) and so $P(S(n))=P(9)=\sum_{i=0}^{m}a_m\cdot9^m$ and $S(P(n))=\sum_{i=0}^{m}S(a_m\cdot9^m)$. Now we know that $n\geq S(n)$ for all non-negative integers $n$ with equality holding only when $n$ is a single digit. Also for $i>1$, since $9^i$ is greater than a single digit number, so $\sum_{i=0}^{m}a_m\cdot9^m=\sum_{i=0}^{m}S(a_m\cdot9^m)$ only if for all $i>1$, $a_i=0$ and $a_1\in\{0,1\}$ and $a_0\in\{0,1,2,3,4,5,6,7,8,9\}$, since for $a_i>1$, $9a_1$ is not a single digit number. Now if $a_1=1$, then we have for all $n>2016$, $S(P(n))=S(n+a_0)=P(S(n))=S(n)+a_0$. Now put $n=10000-a_0$ to get $S(10000)=1=S(10000-a_0)+a_0$. Since $S(10000-a_0)>0$ this is only possible if $a_0=0$. So $P(x)=x$ is a solution. Otherwise $a_1=0$ and so $P(x)=a_0$ where $a_0\in\{1,2,3,4,5,6,7,8,9\}$ since $P(n)$ is positive for $n\geq 2016$. We see that this $P$ also works. Hence we are done. $\square$

Solution with porkemon2. We claim that $P(x) \equiv c$ for $c \in \{1,2,3,4,5,6,7,8,9 \}$ or $P(x) \equiv x$. Plug in $n=10^k$ for large $k$ to get $S(P(10^k))=P(1)$, so $S(P(10^k))$ is constant, so $P$ has only nonnegative integer coefficients, since otherwise we would get a ton of $9$s and as we increase $k$ we get more $9$s. Now we plug in $10^k-1$ for large $k$. This gets us $S(P(10^k-1))=P(9k)$. Note that $P(10^k-1)=O(10^{kd})$, so $S(P(10^k-1))$ is $O(k)$, while $P(9k)=O(k^d)$, so this implies that $d \leq 1$. Let $P(x) \equiv ax+b$. This means that$$S(an+b)=aS(n)+b.$$We plug in $n=10^k+9$ for large $k$ to get$$S(a \cdot 10^k + 9a +b)=10a+b,$$or $S(a)+S(9a+b)=10a+b$. This means $S(9a+b)=9a+b$, since the sum of the digits of a number is at most that number itself. This means $9a+b$ is a single digit number. Then either $a=0,b \in \{1,2,3,4,5,6,7,8,9 \}$ or $a=1,b=0$, which give the desired solution set. (Note that if $a=b=0$ then $P$ won't take positive values.)

Plug in $n=10^k$ for large $k$ . This gives : $$ P(1) = S(P(10^k))$$; implying that all the coefficients of $P(x)$ are non-negative . Now we plug in $n=9\cdot 10^k$ for large $k$ , we have that $$S(P(9 \cdot 10^k))=P(9)$$ Assume $P(x) = \sum_{i=0}^{d} a_i x^i $ with $a_i\ge 0$ Note that $P(9\cdot 10^k)$ is an integer composed of the integers $a_d\cdot 9^d , a_{d-1}\cdot 9^{d-1} \dots a_0 $ with some zeroes between them . So we have $$\sum_{i=0}^{d} S(a_i \cdot 9^i)= S(P(9 \cdot 10^k)) = P(9) = \sum_{i=0}^{d} a_i \cdot 9^i$$ However note that $S(x) \leq x$ , with equality iff $0\leq x \leq 9$ . This means that $0\leq a_i \cdot 9^i \leq 9$ for all $2 \le i \le d$ . In particular , this means that $a_i=0$ for all $i \leq 2$ . Hence $\operatorname {deg} P \leq 1$ . Note that if $P(x) = ax+b$ with $a,b>0$ then we have that $a \leq 1$ . If $a=1$ , then choose $n= 10^k + (10-b)$ . We have : $$ S(P(n))= S( 10^k+10) = 2 \neq 11 = P(11-b) = P(S(n)) \rightarrow \leftarrow$$ This leaves us with $P(x)=x$ for all $x$ or $P(x) = c$ for some $1\leq c \leq 9$ , for all $x$ . Its easy to see that these work . We are done . $\blacksquare$

basic idea is that regrouping is bad, I think? this solution is so awfully written that I'm starting to doubt whether I've actually solved the problem or not We claim that the only such polynomials $P(x)$ are $P(x)=x$ and $P(x)=c$, where $c$ is a positive integer between $1$ and $9$, inclusive. If $P(x)$ has any negative coefficients, $P(10^n)$ for sufficiently large $n$ will contain arbitrarily long chains of $9$s in its decimal representation, so it is impossible for $S(P(10^n))=P(S(10^n))=P(1)$ to be true for all $n$. Therefore, $P(x)$ must contain only nonnegative coefficients. Now we use the case of $n=9999$ to argue the rest. It is important to recognize that, for any nonnegative integers $a$ and $b$, $S(a+b) \leq S(a) + S(b)$, and $S(ab) \leq S(a) \cdot S(b)$. In particular, if any regrouping is involved when computing $a+b$ or $ab$, these inequalities are strict. Now, if we assume $P(x) = a_1 x^{b_1} + a_2 x^{b_2} + \cdots + a_s x^{b_s}$ is degree $2$ or higher, we then have \begin{align*} S(P(9999)) & = S(a_1 \cdot 9999^{b_1} + a_2 \cdot 9999^{b_2} + \cdots + a_s \cdot 9999^{b_s}) \\ & \leq S(a_1 \cdot 9999^{b_1}) + S(a_2 \cdot 9999^{b_2}) + \cdots + S(a_s \cdot 9999^{b_s}) \\ & < a_1 \cdot S(9999)^{b_1} + a_2 \cdot S(9999)^{b_2} + \cdots + a_s \cdot S(9999)^{b_s} = P(S(9999)) \end{align*}where the inequality is strict because $a_i \cdot 9999^{b_i}$ involves regrouping when $b_i \geq 2$, so $S(a_i \cdot 9999^{b_i}) < a_i \cdot S(9999)^{b_i}$. This is a contradiction, so $P(x)$ must be linear or constant. The cases for $P(x)$ linear or constant are different because the regrouping is not necessarily required, so we still need to consider these cases. If $P(x)=c$ for some constant $c$, it must be that $S(c)=c$, which is only true for $c \in \{1, 2, \cdots, 9\}$. These nine solutions are all valid. If $P(x)$ is linear, we can again argue using the case of $n=9999$ by noting that $S(c \cdot 9999) < c \cdot S(9999)$ for all integers $c > 1$, so if the coefficient of $x$ in $P(x)$ were greater than $1$, it would then be that $S(P(9999)) < P(S(9999))$, a contradiction, so we must have $P(x)=x+c$ for some constant $c$. Using $n=9999$ one final time, we see that $c$ must equal $0$, since any larger $c$ would cause regrouping, which would then imply $S(P(9999)) < P(S(9999))$. Therefore, the only linear solution is $P(x)=x$.

I claim that the solutions are $P(x)=x$, or $P(x)=c$ where $c$ is some single digit number, which both clearly work. Lemma: $S(x)\leq x$, with equality at $x\leq 9$ Proof: If $x>10$, then $S(x)\leq x-9<x$, a contradiction. Clearly, if $x\leq 9$, then $S(x)=x$.$\square$ Write $P(x)=a_0+a_1x+a_2x^2+a_3x^3+\dots a_dx^d$. First, plug in $n=10^x$ where $x>a_i$. \[P(1)=P(S(10^x))=S(P(10^x)) \]This gives us that all $a_i\geq 0$ because otherwise we produce 9s Thus, we must have that $a_i=s(a_i)$ and all $a_i$ are nonnegative. Now, we plug in $n=9\cdot 10^{x}$ for some $x$ such that $\forall i, x>a_i$, then we have \[S(P(9\cdot 10^x)) =S(a_0)+S(9\cdot 10^x*a_1)+\ldots S((9*10^x)^d*a_d)= S(a_0)+S(9*a_1)+\ldots S(9^d*a_d)\]\[P(S(9\cdot 10^x)) = P(9)=a_0+9a_1+\ldots 9^da_d\]Since we still have \[S(P(9\cdot 10^x))=P(S(9\cdot 10^x))\]due to our lemma, this tells us that $9^ia_i\leq 9$ for all $i$. This tells us that $a_0\leq 9$ and $a_1\leq 1$, and for $i\geq 2, a_i=0$. Note that if $a_1=0$, then we have the $P(x)=c$ case. We now take $a_1=1$, writing $P(x)=x+a_0$. We now take $n=9999$, which gives \[P(S(9999))=P(36)=36+a_0\]Now, if $a_0=0$, then we have the $P(x)=x$ case, so take $a_0\geq 1$, so \[S(P(9999)) = S(9999+a_0) = S(10000+(a_0-1)) = a_0 < 36+a_0 = P(S(9999))\]A contradiction. Thus, we have shown that $P(x)=x$, and $P(x)=c$ where $c\leq 9$ are the only solutions and we are done$\blacksquare$.

Let $P(x)=a_nx^n+\cdots+a_1x+a_0$. Notice that $S(P(10^k))=P(1)$ Claim 1: All coefficients in $P$ are non-negative Assume the contrary. Clearly, the leading coefficient is positive. Assume the coefficient of $x^{m+1}$ is positive and $x^m$ is negative. As $c$ grows large, we see $a_{m+1}(10^c)^{m+1}+a_m(10^c)^m$ gets many non-zero digits between them. Thus, $S(P(10^c))$ grows arbitrarily large. Contradiction. $\square$ Claim 2: $\deg P \leq 1$ Assume the contrary. For sufficiently large $N$ we have... $S(a_0+9a_1+ \cdots +9^na_n)$ $=S(a_0+(9\cdot 10^N)a_1+\cdots (9 \cdot 10^N)^na_n)$ $=S(P(9\cdot 10^N))$ $=P(9)$ $=a_0+9a_1+ \cdots +9^na_n$ Thus, $P(9)$ is a digit. By assumption, $n \geq 2$. Recall $a_n$ is positive so, $9^na_n \geq 81a_n>10$ which is too large to be a digit. $P(9)>81a_n>10$ so can't be a digit. Contradiction. $\square$ Recall $S(a_0+9a_1)=a_0+9a_1$. If $a_1 \geq 2$ then $S(a_0+9a_1)=a_0+9a_1 >10$ and can't be a digit. So, $a_1$ is $0$ or $1$. If $a_1=0$ then any digit $a_0$ clearly works. If $a_1=1$ we have $a_0+9 \leq 9$ implying $a_0=0$. So, either $P(x)=c$ for some digit $c$ or $P(x)=x$.

Solved over 8 months ago but had to LaTex it so I will post a solution anyways. Let $$P(x) = a_dx^d+a_{d-1}x^{d-1}+....+a_1x+a_0$$$\textbf{Claim:}$ $a_i \geq 0$ for all $d \geq i \geq 1$ $\textbf{Proof)}$ Take some sufficiently large $k > log(max(a_1,...,a_n))$ and let $n=10^k$ for some $k \in \mathbb{N}$, then $$ S(P(10^k)) = P(1)$$and assume FTSOC that $a_i < 0$ is the smallest $i$ satisfying the aforementioned inequality, then we have that the digits $\lceil log(a_{i-1})\rceil+1,...,ki-\lceil log(a_i) \rceil$ are all $9$ and therefore $S(P(10^k))$ can get arbitrarily large which is a contradiction. $\square$ Now, take $n = 9 \cdot 10^k$ for some large $k$ and note that $$\sum_{i=0}^{n} a_i \cdot 9^i = S(9) = S(P(n)) = S(\sum_{i=0}^{n} a_i \cdot 9^i) $$yet, $S(x) = x$ is only possible if $x \in \{0,..,9\}$ meaning that $S$ must be a constant in which case $S(x) = c$ for some $c \in \{0,..,9\}$ or $S(x) = x$. $\blacksquare$

We claim the answers are $P(x)=c$ for $1\le c\le 9$ and $P(x)=x$, which clearly work. Let $P(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0$. We will use the following fact. which is well-known: Fact. If $x_1, x_2, \ldots, x_p$ are nonnegative integers, and $\sum_{i=1}^p S(x_i)=\sum_{i=1}^p x_i$, then both quantities are equal to an integer from $0$ to $9$, inclusive. It is clear that the leading coefficient of $P$ must be positive. Plug in $x=9\cdot 10^j$ into the equation for all sufficiently large values of $j$. We get that $S(P(x))=P(S(x))=P(9)$, which is constant. If any of the coefficients of $P(x)$ are negative, then the sum of $S(P(x))$ for all sufficiently large $n$ cannot be the same (there will be a bunch of nines at one point), so all coefficients of $P$ must be nonnegative. For sufficiently large $j$, there will be no carries between different terms, making $S(P(x))$ simply equal to $\sum_{i=0}^j S(a_i \cdot 9^i)$. However, this must be equal to $P(9)=\sum_{i=0}^j S(a_i \cdot 9^i)$. By the claim, both quantities (particularly $P(9)$) must be equal to an integer from $0$ to $9$, inclusive. Given that the coefficients are positive integers, this reduces the possible values of $P(x)$ to nonnegative integers from $0$ to $9$ and $x$. Clearly $P(x)=0$ does not work, so we are done.

The answer is $P(n) = c$ for integers $1 \leq c \leq 9$ and $P(n) = n$. It is trivial to show that these work. Furthermore, trivially throw out the case where $P$ is constant. Now, write $P(n) = \sum\limits_{i=0}^{d} a_ix^i$, and furthermore define $T$ to be $\{i \mid i \in \mathbb{Z}, 0 \leq i \leq d, a_i \neq 0 \}$ (or, in english, all of the values $i$ such that $a_i$ is not $0$). Say $t_1 < t_2 < t_3 < \ldots < t_e$ are the elements of $T$ sorted in order; in particular, we have $2.718\ldots \neq e = \left|T\right|$. Therefore, we can also write $P(n) = \sum\limits_{i=1}^{e} a_{t_i} x^{t^i}$. Claim: For all integer $1 \leq i \leq d$, $a_i \geq 0$. Proof. Note that this is equivalent to proving that for every $1 \leq j \leq e$, $a_{t_j} > 0$, so we will prove this equivalent restatement. Assume, for the sake of contradiction, that there exists some $j$ where $a_{t_j} < 0$ (the two cannot be equal by definition). Take the largest such $j$. We have two cases: $j = e$, and $j < e$. If $j = e$, we note that $\lim\limits_{n \rightarrow \infty} P(n) = \lim\limits_{n \rightarrow \infty} a_{t_e}n^{t_e} = - \infty$, so if we take a sufficiently large $n$ we will have $P(n) < 0$, contradiction. If instead we have that $j < e$, then we let $n = 10^k$ for some very large $k$. Then, by the problem statement, we have \[ S(P(10^k)) = P(S(10^k)) = P(1) \]which implies that $S(P(10^k))$ must be constant even as $k$ grows large. However, we claim that $S(P(10^k))$ is in fact unbounded. To prove this, write: \[ P(10^k) = \sum\limits_{i=1}^{e} a_{t_i} 10^{kt_i} = \underbrace{a_{t_1}10^{kt_1} + \cdots + a_{t_{j-1}}10^{kt_{j-1}} }_{\text{very small}} + a_{t_j} 10^{kt_j} + \underbrace{a_{t_{j+1}}10^{kt_{j+1}} + \cdots + a_{t_e}10^{kt_e}}_{\text{very big; positive}} \]Then, the first $j$ terms (i.e. the ``very small" terms and $a_{t_j} 10^{kt_j}$) are some negative number with far fewer than $kt_{j+1}$ digits, the number of $0$s present in the ``very big" terms. Thus, when the addition of the two parts (or rather, subtraction of two positive integers) is completed, there will be $\approx k (t_{j+1} - t_j) \geq k$ 9s created in the subtraction, which means the digit sum is unbounded when $k$ is large, contradiction. $\blacksquare$ Claim (Main): The only valid polynomials must be of the form $x+c$ for $0 \leq c \leq 9$. Proof. Assume for the sake of contradiction that $P$ is a valid polynomial not of that form. We use a somewhat similar argument as in the second part of our previous claim. In particular, we take $n = 9 \cdot 10^k$ for $k$ very large. Then, we have: \[ S(P(9 \cdot 10^k)) =S\left(\sum\limits_{i=1}^{e} a_{t_i}9^{t_i}10^{kt_i}\right) = \sum\limits_{i=1}^{e} S\left(a_{t_i}9^{t_i} 10^{kt_i}\right) = \sum\limits_{i=1}^{e} S\left(a_{t_i} 9^{t_i} \right) \]where the second equality holds when $k$ is large enough, because there will be $0$s that ``seperate" each of the $e$ terms of the sum. However, this value is also equal to \[ P(S(9 \cdot 10^k)) = P(9) = \sum\limits_{i=1}^{e} a_{t_i} 9^{t_i}. \]However, it is easy to see (by basic induction, for instance) that $S(x) < x$ when $x \geq 10$. Therefore, if there exists some $a_{t_i} 9^{t_i} > 10$, then \[ \sum\limits_{i=1}^{e} a_{t_i} 9^{t_i} < \sum\limits_{i=1}^{e} S\left(a_{t_i} 9^{t_i}\right), \]contradiction. However, this occurs whenever $t_i > 2$, or if $i = 1$ and $a_{t_i} \geq 2$, or if $i = 0$ and $a_{t_i} \geq 10$, which proves the claim. $\blacksquare$ Now, we can finally finish by showing that the polynomial $P(n) = n+c$ fails the given conditions. This is easy enough to see by plugging in the value $10^4 - c$; it is clear that \[ 37 = P(S(10^4 - c)) \neq S(P(10^4 - c)) = 1 \]and we are finally done.

The answer is $P(x)=x$ and $P(x)=c$ for all integers $1\le c\le 9$. It's easy to show that these work. Now suppose that the degree of $P$ is at least $2$. Consider $n=10^a-1$ for sufficiently large $a$. Then let the term with the largest degree in $P(x)$ be $cx^k$. Note that $S(n)=9a$ while $P(n)<10c(10^a-1)^k$ since $a$ is sufficiently large (which causes the effects of terms of smaller degree to be negligible). We have that the digit sum of $P(n)$ is, say, at least $\frac{c(9a)^k}{10}$ (since $a$ is sufficiently large). Suppose that $10c(10^a-1)^k$ has $d$ digits. Then we must have that $9d\ge \frac{c(9a)^k}{10}$. But now, the LHS increases linearly and since $k\ge 2$ this inequality must be violated for sufficiently large $a$. Now suppose that $P$ is constant. Then it's easy to show that if $P(x)=c$ we must have $1\le c\le 9$. Finally, suppose that $P$ is linear. Let $P(x)=ax+b$. Take $n=9999$ to get \[36a+b=S(9999a+b).\]It follows that $9999a+b$ has at least $4a+\frac{b}{9}$ digits. Then, we have \[9999a+b\ge 10^{4a+\tfrac{b}{9}-1}.\]Fix $a\ge 2$. I claim that we must have \[10^{4a+\tfrac{b}{9}-1}>9999a+b.\]Clearly this holds for $b=0$. Incrementing $b$ by $1$ multiplies the LHS by $10^{\tfrac{1}{9}}$ and increases the RHS by $1$. The LHS will increase by at least $10^7\left(10^{\tfrac{1}{9}}-1\right)$. Therefore, it suffices to show that \[10\ge (10^{-7}+1)^9\]which is true by the Binomial Theorem. Finally, we must have $a=1$, which implies that $S(n)+b=S(n+b)$ for all $n\ge 2016$. Take $n=10^x-b$ for sufficiently large $x$; then the RHS is $1$ while the LHS is at least $b+1$. Then $b=0$ which gives $P(x)=x$. We are done. $\blacksquare$

Let $y\ge 4$ be an integer and $x\in\{0,1,2\dots,9\}$ then we have \[S(P(x\cdot 10^y))=P(x).\]Let $S(n)=a_mn^m+a_{m-1}n^{m-1}+\dots+a_1n+a_0$ and let $y$ be large enough so that $10^y$ exceeds $|a_mx^m|+|a_{m-1}x^{m-1}|+\dots+|a_1x|+|a_0|.$ Then, we claim the value $P(10^y)$ will be \[\overline{a_ma_{m-1}\dots a_0}.\]This holds unless there are negative terms, but if there are negative terms then increasing $y$ would result in more nines being added, contradicting $S(P(10^y))=P(1).$ Thus, we know that $P(x)$ has nonnegative coefficients and that \[S(P(x\cdot 10^y))=S(a_0)+S(xa_1)+S(x^2a_2)+\dots+S(x^ma_m)=P(x)=a_0+xa_1+\dots+x^ma_m\]Note that $S(c)\le c$ for all $c$ with equality if and only if $c\in\{0,1,2,\dots,9\}$ so $S(a_0)=a_0,S(xa_1)=xa_1, S(x^ia_i)=x^ia_i.$ Now, this implies $a_0\in \{0,1,\dots,9\}$ and letting $x=9$ we get $a_1\in \{0,1\}$ and $a_i=0$ for $i\ge 2.$ Thus, $P(x)=c,c\in\{0,1,\dots,9\}$ or $P(x)=x+c,c\in\{0,1,\dots,9\}.$ The second option yeilds \[S(x+c)=S(x)+c\]but simply use something like $10^y-1$ to ensure that only $c=0$ is possible option. Now, checking shows that the possible solutions are: $P(x)=c,c\in\{1,\dots,9\}$ or $P(x)=x.$

The solutions are $P(x)=c$ where $c \in \{ 1,2,3, \dots , 9\}$, and $P(x)=x$. Let $P(x)=a_dx^d+a_{d-1}x^{d-1} + \cdots + a_0$. Let $b \ge 4$ be an integer. Take $n=10^b$ so that $S(P(10^b))=P(1)$. If there is negative coefficients, take $b$ to be very big so that $\frac{a_i}{a_{i-1}} >> 10^b$ for all $i$. The negative term will make an arbitrarily large amount of $9$'s appear, so $P(1)$ is arbitrarily big, a contradiction since it is fixed. Thus all coefficients are nonnegative. We have that $P(10^b)=\overline{a_d 0 \dots 0 a_{d-1} 0 \dots 0 a_1 0 \dots 0 a_0}$. We have that $\sum_{i=0}^d a_i = P(1) = S(P(10^b)) = \sum_{i=0}^d S(a_i)$. Since $S(a_i) \le a_i$ with equality iff $a_i \in \{0,1,2 \dots , 9 \}$, so all the coefficients are one digit integers. Take $n=10^b \cdot \underbrace{1 1 \dots 1}_{10}$ with $b$ big enough. We have that $$\overline{a_da_{d-1} \dots a_0} = P(S(n)) = S(P(10^b \cdot \underbrace{1 1 \dots 1}_{10})) = S(\overline{\underbrace{a_d \cdots a_d}_{10} 0 \dots 0 \underbrace{a_{d-1} \cdots a_{d-1}}_{10} 0 \dots 0 \underbrace{a_1 \cdots a_1}_{10} 0 \dots 0 \underbrace{a_0 \cdots a_0}_{10}} = 10(a_d+a_{d-1}+ \cdots +a_0).$$If $d \ge 2$, then $81 \ge 9a_0 \ge 90 a_2 \ge 90$, a contradiction. If $d=0$, we obviously get the desired solutions. Now assume $P(n)=an+b$ with $a,b \in \{0,1,2, \dots , 9\}$. We have $aS(n)+b=S(an+b) \le S(an)+b \le aS(n)+b$. Thus $S(an+b)=S(an)+b$ and $aS(n)=S(an)$. Taking $n=9$ into the second equation we have $9a$ is a one digit integer, so $a=1$. Thus $S(n+b)=S(n)+b$. Taking $n=9$ again, we have $b=0$, so we get $P(x)=x$ is the only degree $1$ solution so we are done.

Fakesolve? My solution looks different than others, suspicious imo Let $P(x)=\sum a_dx^d$ as usual and note that $a_d$ is positive since for bigger $x$ $P(x)$ should be positive. Assume $ d \ge 1$ since if $P$ is polynomial, it is clear that $P(x)=c \ \forall c \in \{1,2,...,9 \} $ works. Choose $n=\overline{b_k000...000b_{k-1}000..000b_{k-2}000...b_0} \cdot 10^e$ such that $\sum b_i= 10^m$ and $b_i \neq 0$. Now, choose arbitrarly bigger $k,e,m$ and arbitrarly bigger number of zeroes between $b_i,b_{i-1}$ hence $n$ is arbitrarly bigger. Since by choice of $n$, if we multiply $n$ by some natural number, say $N$, then $N \cdot n$ will be equal $\overline{ (b_kN)000.000 (b_{k-1}N)000...000....000 (Nb_0)} \cdot 10^e$. Then $S(N \cdot n)= \sum b_iN= N \sum b_i= N \cdot 10^m$. Now lets calculate RHS. Note that $S(n)=10^m$ by choice of $n$. Then $P(10^m)=\overline{a_d00...0a_{d-1}00...000....00a_0}$ since $m$ is very big. Now, calculate LHS: $P(n)=\sum a_dn^d$. Note that by $10^e$, there are some zeroes between $a_in^i$ and $a_{i-1}n^{i-1}$. Then $S(P(n))=\sum S(a_in^i)$. By choice of arbitrarly bigger number of zeroes between digits, we can calculate $a_in^i$ as letting $N_i= a_in^{i-1}$, then $S(a_in^i)=S(N_i \cdot n)= N_i \cdot 10^m$. Doing the same thing repeteadly, We have $LHS= \overline{(N_d10^m)00...0000(N_{d-1}10^m)00...000.....a_0}$ while $RHS= \overline{a_d00...0a_{d-1}00...000....00a_0}$. The first digit from left of $RHS$ is $a_d$, hence the first digit of $a_dn^{d-1}=N$ is $a_d$. Then by choice of $n$ we must have $d=1$. After that, let $x=9 \cdot 10^d$ to conclude $\boxed{P(x)=x}$ is a possible solution, and it works hence we are done! Note: uhh I just realized we should prove $a_i$ must be non-negative, it is fixable anyways

We claim that only solutions are $P(x)=x$ and $P(x)=c$ for $c\in \mathcal A \left \{ 1,2,\dots,9 \right \},$ which obviously work. Consider some satisfying polynomial $P(x)=\sum_{k=1}^d a_kx^k.$ Since $P$ is positive for arbitrary large integer $x\geq 2016$ it follows that $a_d>0.$ Plug $n=9\cdot 10^E$ for an arbitrary large $E;$ if $\exists b:a_b<0$ then the decimal representation of $P(n)$ contains a sufficently long substring consisting of digits $9,$ so $S(P(n))=P(9)$ is unbounded, contradiction; hence $a_i\geq 0.$ Then the decimal representation of $P(n)$ is a sequence of numbers $a_k9^k$ (for $k=1,2,\dots,d$) separated by zeroes; therefore $$\sum_{i=1}^d a_i9^i=P(9)=S(P(n))=\sum_{i=1}^d S(a_i9^i).$$Since for $m\in \mathbb Z^+$ we have $S(m)\leq m$ with holding equality only for $m\in \mathcal A,$ it follows that $a^k 9^k\in \mathcal A$ for each $k.$ Therefore $$a_0\in \mathcal A,\text{ } a_1\in \left \{ 0,1 \right \},\text{ }a_{i>1}=0,$$so it suffices to check all cases.

Solved with cxyerl. The answer is $\boxed{P(n)\equiv 1,2,3,4,5,6,7,8,9,n}$. For what follows, let $k$ be a sufficiently large positive integer. I think $k=10^{665}\cdot(665^{\deg P}\cdot(\text{sum of the absolute values of all coefficients of P}+10^{665})+665)$ is good enough. Claim. All of the coefficients of $P$ are nonnegative integers. Proof. Obviously the leading coefficient is nonnegative. Assume FTSOC that some coefficient of $P$ is negative. Consider some positive integer $h>k$. If $n=10^{h}$, then $P(n)$ should have many $9$s in its decimal expansion. By increasing $h$, we can get arbitrarily many $9$s, therefore bloating $S(P(n))$ to infinity. However, $P(S(n))=P(1)$ is constant, contradiction. Let $n=9\cdot 10^k$. Then \[P(9)=S(a_0)+S(9a_1)+S(81a_2)+\dots\le a_0+9a_1+81a_2+\dots=P(9),\]equality case being $a_0$, $9a_1$, $81a_2$, etc all being a digit in base $10$, so $a_2=a_3=\dots=0$. This also means that $0\le a_0\le 9$ and $a_1\in\{0,1\}$. If $a_1=0$ then only $1\le a_0\le 9$ work, and if $a_1=1$ then $n=10^k+9$ gives $a_0=0$, which works. QED. Remark. I had a really weird bounding solution beforehand, but cxyerl found a much cleaner finish!

Note, the only constant polynomials that satisfy are $P\equiv c$ where $c\in\{1,2,\ldots,9\}$. Moreover, $P(n)=n$ satisfies as well. We claim that these are the only solutions. Note that $n-S(n)\mid P(n) - P(S(n))$. So, $n-S(n)\mid P(n)-S(P(n))$. So, if $1\leq n\leq9$, then $1\leq P(n)\leq9$. More importantly, $P(9)\leq9$. Suppose $P(n)=a_0+a_1n+\cdots+a_kn^k$ Fix $n=9\times10^j$, where $j$ is large enough. Then, $S(n)=9$ and we have $n-9\mid P(n)-S(P(n))$. We take $j$ to be so large that there is no carry-over in the addition $a_0+a_1n+\cdots+a_kn^k$. Then, we have $S(P(n))=S(a_0)+S(a_1n)+\cdots+S(a_kn^k)=S(a_0)+S(9a_1)+\cdots+S(a_k9^k)$ Since $S(n)=9$, we have $S(P(n))=P(9)$. This gives $a_0+9a_1+\cdots+a_k9^k=P(9)=S(a_0)+S(9a_1)+\cdots+S(a_k9^k)$ Note that $S(n)\leq n$ and equality holds iff $1\leq n\leq9$. So, we have $\{a_0,9a_1,\ldots,a_k9^k\}\subseteq\{1,2,\ldots,9\}$ which forces $a_2=a_3=\cdots=a_k=0$ and $a_1\in\{0,1\}$ and $1\leq a_0\leq 9$. Checking gives the solutions mentioned. $\square$

The answer is $P(x)=c$ where $1 \leq c \leq 9$ and $P(x)=x$, which clearly work. Suppose that $P(x)=a_dx^d+\cdots+a_0$. Clearly $a_d$ is positive. Furthermore, by plugging in $n=10^k$ for large $k$, , we get that each coefficient is nonnegative, since if a negative coefficient exists by making $k$ large we may produce an unbounded number of digits equal to $9$ in $P(10^k)$, but $P(S(10^k))=P(1)$ is constant. Then, by plugging in $n=9\cdot 10^k$, we get that $S(P(9\cdot 10^k))=S(9^da_d)+\cdots+(9^0a_0)$ and $P(S(9\cdot 10^k))=P(9)=9^da_d+\cdots+9^0a_0$, hence each $9^ia_i$ must be at most $9$, implying that either $i=1$ and $a_i=1$ or $i=0$ and $a_i \leq 9$. Therefore we only have to prove that $P(x)=x+c$ for some $1 \leq c \leq 9$ is impossible. This is trivial by plugging in $n=10-c$. $\blacksquare$

Claim: $P$ must be linear. Proof. Let $P(n) = a_d x^d + a_{d-1} x^{d-1} + \dots + a_0$. Consider $n = c \cdot 10^N$. For a sufficiently large $N$, it follows that \[ \sum_{i=0}^{d} S(a_i \cdot c^i) = P(S(c)) \]As such, it follows that for $c = \overline{1111111 \dots 1}$ with $k$ $1$s, that for sufficiently large $N$ \[ \sum_{i=0}^{d} S(a_i \cdot k^i) = \sum_{i=0}^{d} S(a_i \cdot (10^{Nk} + \dots + 1)^i) \]Since $S(a) + S(b) \ge S(a + b)$, the RHS must be strictly greater, and inequality only holds when no caries occur when combining the right hand side. If $i > 1$, a contradiction arises from taking $k > 10$, after which a carry must occur. $\blacksquare$ As such, let $P(x) = ax + b$ so $S(ax + b) = aS(x) + b$. As such, there again must be no carries when evaluating $S(ax + b)$, which only holds when either $a = 0$, and $S(b) = b$, or $a = 1$ and $b = 0$.

The answer is $P(x)=x$ or $P(x)=k$ for $k=1,2,3,4,5,6,7,8,9$, which work. Let $P(x)=\sum_{i=1}^j a_ix^i$. Claim: Every coefficient in $P$ is nonnegative Proof. Note that the leading coefficient is positive as if not taking $S(n)$ sufficiently large gives a sign contradiction. Then, letting $n=10^k$ for large enough $k$ we obtain that by increasing $k$ we can get more and more $9$s in the decimal representation of $P(n)$ as there is a negative signed term directly following a positive signed one that is arbitrarily larger than it. $\blacksquare$ Claim: $P$ has degree $0$ or $1$. Proof. Take $n=9\cdot 10^k$ again for sufficiently large $k$. Then, $P(S(n))=P(9)=\sum_{i=1}^ja_i9^i$. However, $S(P(n))=\sum_{i=1}^j S(a_i\cdot 9^i)$ since for large enough $k$ each $a_i 9^i$ doesnt overlap digits with any other. Then, $a_i\cdot 9^i\geq S(a_i\cdot 9^i)$ with equality iff $a_i\cdot 9^i$ is a single digit, but equality must hold everywhere from above. This implies that $d=\deg P\leq 1$ as if not $a_d\cdot 9^d>S(a_d\cdot 9^d)$. $\blacksquare$ Now, if $P$ is constant then $P(x)=1,2,\dots,9$. If not, then $P(x)=a_1x+a_0.$ From above, we know that $a_1\cdot 9_i$ is a single digit and hence $a_1=1$. Then, if $a_0\neq 0$ simply take $n=10^k-a_0$ to get a contradiction. Thus $P(x)=x$ or $P(x)=k$ for $k=1,2,3,4,5,6,7,8,9$, as desired.

Idea is to fix $S(n)$. Take $n=10^k$. Then, $S(n)=1$ and RHS is constant, which is $P(1)$. Let $P(x) = c_0 + c_1x + \cdots + c_dx^d$. Then, for arbitrarily large $k$, we have \[S(P(10^k))=S(c_0)+S(c_1)+\cdots+S(c_d)=c_0+c_1+\cdots+c_d\]Similarly, for any $10>c>0$, we have for sufficiently large $k$, \[S(P(c\cdot 10^k))=S(c_0)+S(cc_1)+\cdots+S(c_dc^d)=c_0+c_1c+\cdots+c_dc^d\]Hence, $c_i=0$ for $i>1$ and $c_1=0,1$. Only constant polynomials are one digit constants. The only linear polynomial is $x+t$, and plugging in original equation gives $t=0$. So, $P(x)=x$. Hence, \[P(x)\in\left\{x,1,2,\ldots,9\right\}\]

Answer: $P(x) = x$ or $P(x) = c$, where $c \in \{1, 2, \dots, 9\}$. Firstly, we'll show that $\deg(P) \le 1$. Assume the contrary, let $P(x) = a_kx^k + a_{k-1}x^{k-1} + \dots + a_1x + a_0$ for some $k \ge 2$. Replacing $P(x) \to -P(x)$, we may assume $a_k > 0$. Let $N$ be a large enough number and take $n = 10^N - 1$. Then $S(n) = 9N$, so $P(S(N)) = P(9N)$ and $P(n) < (a_k+1)n^k < (a_k + 1)10^{Nk}$. Since $PS(P(n)) \le 9(\log_{10}(P(n)) + 1) < 9(\log_{10}(a_k + 1) + Nk + 1)$, we see that $P(9N) < 9Nk + c$ for some constant $c$, contradicting the fact that $N$ is large enough and $\deg(P) \ge 2$. Thus, we may assume $\deg(P) \le 1$. Case 1: $\deg(P) = 1$. Let $P(x) = ax + b$ for some $a, b \in \mathbb{Z}$. Take $n = 10^N + k$ for some large $N$ and some $k \ge 2016$. Then, $a + S(ak + b) = a + aS(k) + b = aS(n) + b = S(an + b) = S(a) + S(ak + b)$, so $a = S(a)$, which means that $a \in \{1, 2, \dots, 9\}$. Thus taking $n = 10^N + k$ for some large $N$, we get that $a + aS(k) + b = aS(n) + b = S(an + b) = S(a) + S(ak + b) = a + S(ak + b)$, so $aS(k) + b = S(ak + b)$ for all $k \ge 0$. Plugging $k = 0$ into this, we see that $b = S(b)$, which means that $b \in \{1, \dots, 9\}$. Now for $0 \le k \le 9$, $ak + b = S(ak + b)$, so $9a + b \in \{0, 1, \dots, 9\}$ and $9a + b \ge 9$, so $a = 1$ and $b = 0$, which means that $P(x) = x$. Case 2: $\deg(P) = 0$. In this case, we get that $c = P(x) = S(c)$, so $c \in \{0, 1, \dots, 9\}$. So $P(x) = x$ or $P(x) = c$ for some $c \in \{1, \dots, 9\}$. $\blacksquare$

I claim the solutions are $P(x) = c$ for $1 \le c \le 9$ and $P(x) = x$, both of which clearly work. Let $n = 9999999 \dots$ where the $9$ is repeated $k$ times. Then $P(S(n)) = P(9k)$. Now $S(P(n)) \le (9 \log P(n) + 1) \sim 9k + a$ for some constant $a$. Since the $S(P(n))$ is linear or smaller in $k$, we see that $P(S(n)) = P(9k)$ is linear or smaller in $k$, so $P$ is linear. We then have $cS(n) + d = S(cn + d)$. Substitute $n = 9$, then have $9c + d = S(9c + d)$, this only has single digit solutions (manually observe that $10$ thru $20$ has no solutions, after that all $2$ digits have sum at most $18$ but the value is greater than $20$, after that we generally have $9k < 10^{k- 1}$), so we have $9c + d \ge 9 $, so either we have $c = 0$ and $d$ a single digit, giving the working constant solutions, otherwise we have $c = 1, d = 0$, giving $P(x) = x$, which works.

Let $P(x) = a_mx^n+a_{m-1}x^{m-1}+\cdots + a_1x^1+a_0.$ Suppose for the sake of a contradiction that there is some $a_i < 0.$ Letting $n=10^k$ for some arbitrarily large positive integer $k$ gives $P(1)=S(P(10^k)).$ But as $k$ increases $P(10^k)$ gets more and more $9$s and hence its sum of digits goes to infinity, a contradiction. Therefore all $a_i \geq 0.$ Now, notice that letting $n=9 \cdot 10^k$ for some arbitrarily large positive integer $k$ yields $$\sum_{i=0}^n S(a_i9^i) = P(9) = \sum_{i=0}^n a_i9^i.$$However, note that if a positive integer $x$ has $d \geq 3$ digits then $$S(x) \leq 9d < 10^{d-1} \leq x.$$Meanwhile, if $d=2$ and $x > 18$ then $S(x) \leq 18 < x.$ If $10 \leq x \leq 18,$ we have $S(x) \leq 1+8 = 9 < x.$ Therefore, for all $x \geq 10$ we have that $S(x) < x.$ Meanwhile for $1 \leq x \leq 9$ clearly $S(x) = x.$ With this, if $n \geq 2$ we clearly have $$\sum_{i=0}^n S(a_i9^i) < \sum_{i=0}^n a_i9^i,$$which is a contradiction. Thus $n \leq 1,$ in this case equality must hold so we have $S(a_0)=a_0$ and $S(9a_1)=9a_1.$ From the first equation, we have $0 \leq a_0 \leq 9.$ From the second equation, we have $a_1 = 0,1.$ If $a_1=0,$ $P(x)=a_0$ and this clearly works. If $a_1=1,$ $P(x)=x+a_0.$ If $1 \leq a_0 \leq 9,$ then letting $n=10-a_0$ yields $$a_0+S(10-a_0)=S(10)=1$$which is clearly impossible. Thus $a_0 = 0$ and $P(x)=x.$ This solution clearly works. Hence, the only solutions are $P(x)=a_0$ where $0 \leq a_0 \leq 9$ or $P(x)=x.$