How many natural numbers $n$ less than $10^{6}$ are there such that the sum of the digits of $n$ is even, and the sum of the digits of $(n+1)$ is also even


I. solution. At first glance, it is surprising that when transitioning from $n$ to $(n+1)$, the sum of the digits must remain even, or in other words, must change by an even number; after all, we would consider it natural for the digit sum to increase by 1 with the increment. Indeed, this is the more common case - namely, if the last digit of $n$ is not 9 - because in this case only the last digit changes by 1, an odd number, and therefore the digit sum changes from even to odd or vice versa; hence, there is nothing to look for here. However, the problem often presents itself in the less frequent cases, namely with $n$ ending in 9, when at least two new digits appear at the end of the $(n+1)$ number.

Let us denote the number of 9s at the end of the number $n$ by $k$, that is, the $(k+1)$-th digit from the right is not a 9. When transitioning to $(n+1)$, this digit increases by 1, and then $k$ zeros follow - that is, they are 9 less - so the change in the digit sum is $(1-9k)$. This is clearly even if and only if $k$ is odd. - According to this, the smallest suitable $n, (n+1)$ pair with 1 9 is 19 and 20, with 3 9s it is $1999, 2000$.

Since $n<10^{6}$, that is, it has at most 6 digits, $k$ must also satisfy $k \leq 5$ in our problem.

I. If $k=5$, then $n$ is of the form $A 99999$, where $A=1,3,5$ or 7, since the sum of the digits $A+5 \cdot 9$ is only even with an odd $A$, and on the other hand $A \neq 9$; the number of such $n$s is therefore 4.

II. If $k=3$, then $n$ is of the form $A B C 999$, where $A+B+C$ is odd and $C \neq 9$. Due to the latter condition, $C$ can be any of the digits $0,1, \ldots, 8$, that is, 9 ways, $B$ in 10 ways, and finally the digit $A$ can make the already determined $(B+C)$ odd in 5 ways: with the digits $0,2,4,6,8$ if $(B+C)$ is odd, and with the 5 odd digits if $(B+C)$ is even. Thus, 450 suitable $n$s belong to this group.

III. Finally, if $k=1$, similarly $n=A B C D E 9$, where $E<9$ and $(A+B+C+D+E)$ is odd; repeating the reasoning of case II, here $5 \cdot 10^{3} \cdot 9=45000$ suitable $n$s belong.

Based on all this, the answer to the question is: $45000+450+4=45454$ natural numbers less than $10^{6}$ have an even digit sum such that the digit sum of $(n+1)$ is also even.

II. solution. If we already know that $n$ can only be suitable if an odd number of 9s is followed by a digit different from 9, then the determination of the number of suitable ones can also be carried out as follows, for any $j$ up to the limit of $10^{j}$.

If $j$ is odd, then a maximum of $(j-2)$ 9s can appear at the end of $n$, since a number written with $j$ 9s cannot be preceded by a digit that would make the odd $9j$ sum even; if, on the other hand, $j$ is even, then numbers ending in $(j-1)$ 9s are still possible. The number of natural numbers that are less than $10^{j}$ and in which 9 stands in the last $s$ places - regardless of what digit stands immediately in front of them - is obviously $N_{s}=10^{j-s}$, since all numbers that can be written with $(j-s)$ digits, allowing a zero to stand in all $(j-s)$ places, appear in sequence before the last $s$ places. Thus, the number of numbers whose last $s$ digits are exactly $s$ 9s is $N_{s}-N_{s+1}=10^{j-s}-10^{j-s-1}=9 \cdot 10^{j-s-1}$.

We will show that among these numbers, just as many have an even digit sum as have an odd one - unless $N_{s+1}$ is also an even number, that is, $j-s-1 \geq 1$, or $s \leq j-2$; more precisely, that this statement is true for the $(j-s)$-digit and $(j-s-1)$-digit numbers separately, and thus also for the set that remains after omitting the $N_{s+1}$ number. Indeed, because $j-s-1 \geq 1$, even the $(j-s-1)$-digit numbers can be grouped into ten-member groups starting from 0 and increasing by one, the ten numbers in each group differ only in the last digit, and among the last digits, 5 make the sum of the common digits in front of them odd, and 5 make it even. And this equality remains even if we write 9s behind them. According to this, the number of $j(\geq s+2)$-digit numbers ending in exactly $s$ 9s and having an even digit sum is

$$
\frac{N_{s}}{2}-\frac{N_{s+1}}{2}=5 \cdot 10^{j-s-1}-5 \cdot 10^{j-s-2}=45 \cdot 10^{j-s-2}
$$

if

$$
j-s-2 \geq 0, \quad \text { that is } \quad s \leq j-2
$$

We consider this for the odd $s$ values (the $k$ values in the first solution), so for $s=1,3,5, \ldots$ the exponents of 10 will be: $j-3, j-5, j-7, \ldots$, and considering the decrease by 2, the sum of the (*) numbers will be in the form $454545 \ldots$. If $j$ is odd, then for $s=j-2$ (*) gives $45 \cdot 10^{0}$, that is, 45, so 45 also stands at the end of the sum, the number of digits is $(j-1)$, and the number of "45" digit pairs is $\frac{j-1}{2}$.

If, on the other hand, $j$ is even - as in our original problem with $j=6$ - then our halving consideration is still valid for $s=j-1$, but $N_{s+1}$ cannot be halved, this value is 1, the number of numbers ending in $(s+1)=j$ 9s. The number $n$ written with $j$ 9s is still less than $10^{j}$ and its digit sum $9j$ is also an even number, but it does not meet the condition, because then $n+1=10j$, and the sum of its digits is 1, not even. According to this, for $s=j-1$ we get $5-1=4$ instead of (*), so the number of $n$s meeting the condition of the problem is given by the $(j-1)$-digit number $4545 \ldots 4$.

In summary: the number of suitable $n$s up to $10^{j}$ is the following $(j-1)$-digit number: $4545 \ldots$