Solution

Answer: No. For any such polynomial there exists a positive integer \(k\) such that \(s(k)\) and \(s(P(k))\) have different parities.

With the notation above, we begin by choosing a positive integer \(t\) such that

\[10^{t}>\max \left\{\frac{100^{n-1} a_{n-1}}{\left(10^{\frac{1}{n-1}}-9^{\frac{1}{n-1}}\right)^{n-1}}, \frac{a_{n-1}}{9} 10^{n-1}, \frac{a_{n-1}}{9}\left(10 a_{n-1}\right)^{n-1}, \ldots, \frac{a_{n-1}}{9}\left(10 a_{0}\right)^{n-1}\right\}\]

As a direct consequence of \(10^{t}\) being bigger than the first quantity listed in the above set, we get that the interval

\[I=\left[\left(\frac{9}{a_{n-1}} 10^{t}\right)^{\frac{1}{n-1}},\left(\frac{1}{a_{n-1}} 10^{t+1}\right)^{\frac{1}{n-1}}\right)\]

contains at least \(100\) consecutive positive integers. Let \(X\) be a positive integer in \(I\) such that \(X\) is congruent to \(1 \bmod 100\). Since \(X \in I\) we have

\[9 \cdot 10^{t} \leqslant a_{n-1} X^{n-1}<10^{t+1}\]

thus the first digit (from the left) of \(a_{n-1} X^{n-1}\) must be \(9\). Next, we observe that \(a_{n-1}\left(10 a_{i}\right)^{n-1}<9 \cdot 10^{t} \leqslant a_{n-1} X^{n-1}\), thus \(10 a_{i}<X\) for all \(i\), which immediately implies that \(a_{0}<a_{1} X<\cdots<a_{n} X^{n}\), and the number of digits of this strictly increasing sequence forms a strictly increasing sequence too. In other words, if \(i<j\), the number of digits of \(a_{i} X^{i}\) is less than the number of digits of \(a_{j} X^{j}\). Let \(\alpha\) be the number of digits of \(a_{n-1} X^{n-1}\), thus \(10^{\alpha-1} \leqslant a_{n-1} X^{n-1}<10^{\alpha}\). We are now going to look at \(P\left(10^{\alpha} X\right)\) and \(P\left(10^{\alpha-1} X\right)\) and prove that the sum of their digits has different parities. This will finish the proof since \(s\left(10^{\alpha} X\right)=s\left(10^{\alpha-1} X\right)=s(X)\). We have \(P\left(10^{\alpha} X\right)=10^{\alpha n} X^{n}+a_{n-1} 10^{\alpha(n-1)} X^{n-1}+\cdots+a_{0}\), and since \(10^{\alpha(i+1)}>10^{\alpha i} a_{n-1} X^{n-1}>\) \(10^{\alpha i} a_{i} X^{i}\), the terms \(a_{i} 10^{\alpha i} X^{i}\) do not interact when added; in particular, there is no carryover caused by addition. Thus we have \(s\left(P\left(10^{\alpha} X\right)\right)=s\left(X^{n}\right)+s\left(a_{n-1} X^{n-1}\right)+\cdots+s\left(a_{0}\right)\). We now look at \(P\left(10^{\alpha-1} X\right)=10^{(\alpha-1) n} X^{n}+a_{n-1} 10^{(\alpha-1)(n-1)} X^{n-1}+\cdots+a_{0}\). Firstly, if \(i, then \(a_{n-1} X^{n-1}\) has more digits than \(a_{i} X^{i}\) and \(a_{n-1} X^{n-1} \geqslant 10 a_{i} X^{i}\). It now follows that \(10^{(\alpha-1)(i+1)+1}>10^{(\alpha-1) i} a_{n-1} X^{n-1} \geqslant 10^{(\alpha-1) i+1} a_{i} X^{i}\), thus all terms \(10^{(\alpha-1) i} a_{i} X^{i}\) for \(0 \leqslant i \leqslant n-1\) come in 'blocks', exactly as in the previous case. Finally, \(10^{(\alpha-1) n+1}>10^{(\alpha-1)(n-1)} a_{n-1} X^{n-1} \geqslant 10^{(\alpha-1) n}\), thus \(10^{(\alpha-1)(n-1)} a_{n-1} X^{n-1}\) has exactly \((\alpha-1) n+1\) digits, and its first digit is 9 , as established above. On the other hand, \(10^{(\alpha-1) n} X^{n}\) has exactly \((\alpha-1) n\) zeros, followed by 01 (as \(X\) is \(1 \bmod 100\)). Therefore, when we add the terms, the 9 and 1 turn into 0 , the 0 turns into 1 , and nothing else is affected. Putting everything together, we obtain

\[ s\left(P\left(10^{\alpha-1} X\right)\right)=s\left(X^{n}\right)+s\left(a_{n-1} X^{n-1}\right)+\cdots+s\left(a_{0}\right)-9=s\left(P\left(10^{\alpha} X\right)\right)-9 \]

thus \(s\left(P\left(10^{\alpha} X\right)\right)\) and \(s\left(P\left(10^{\alpha-1} X\right)\right)\) have different parities, as claimed.