International Mathematical Olympiad

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}(10a_{n-1}{)}^{n-1},\dots ,\frac{a_{n-1}}{9}(10a_0{)}^{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\mathrm{mod}100$. Since $X\in I$ we have $$9\cdot 10^t⩽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}(10a_i{)}^{n-1}<9\cdot 10^t⩽a_{n-1}{X}^{n-1}$, thus $10a_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}⩽a_{n-1}{X}^{n-1}<10^{\alpha }$. We are now going to look at $P(10^{\alpha }X)$ and $P(10^{\alpha -1}X)$ and prove that the sum of their digits has different parities. This will finish the proof since $s(10^{\alpha }X)=s(10^{\alpha -1}X)=s(X)$. We have $P(10^{\alpha }X)=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(P(10^{\alpha }X))=s(X^n)+s(a_{n-1}{X}^{n-1})+\cdots +s(a_0)$. We now look at $P(10^{\alpha -1}X)=10^{(\alpha -1)n}{X}^n+a_{n-1}10^{(\alpha -1)(n-1)}{X}^{n-1}+\cdots +a_0$. Firstly, if $i<n-1$, then $a_{n-1}{X}^{n-1}$ has more digits than $a_i{X}^i$ and $a_{n-1}{X}^{n-1}⩾10a_i{X}^i$. It now follows that $10^{(\alpha -1)(i+1)+1}>10^{(\alpha -1)i}{a}_{n-1}{X}^{n-1}⩾10^{(\alpha -1)i+1}{a}_i{X}^i$, thus all terms $10^{(\alpha -1)i}{a}_i{X}^i$ for $0⩽i⩽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}⩾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\mathrm{mod}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(P(10^{\alpha -1}X))=s(X^n)+s(a_{n-1}{X}^{n-1})+\cdots +s(a_0)-9=s(P(10^{\alpha }X))-9$$ thus $s(P(10^{\alpha }X))$ and $s(P(10^{\alpha -1}X))$ have different parities, as claimed.