Estonian Mathematical Olympiad

Let $\overline{a_1{a}_2...a_n}$ be an $n$-digit number such that the sum of the number with the number obtained by reversing its digits is a palindrome. We consider two cases separately.

If the sum is an $n$-digit number, then obviously $a_1+a_n<10$. We show that no carry occurs when adding the numbers $\overline{a_1{a}_2...a_n}$ and $\overline{a_n{a}_{n-1}...a_1}$. Suppose, to the contrary, that a carry occurs. Let the result of the addition be the number $\overline{b_1{b}_2...b_n}$, with the first carry occurring in the $i$-th position from the end. Then $a_n+a_1=b_n$, $a_{n-1}+a_2=b_{n-1}$, $\dots$, $a_{n+1-(i-1)}+a_{i-1}=b_{n+1-(i-1)}$ and $a_{n+1-i}+a_i\ge 10$. Due to the last inequality, a carry also occurs in the $(n+1-i)$-th position from the end. Therefore, $b_{i-1}=a_{i-1}+a_{n+1-(i-1)}+1=b_{n+1-(i-1)}+1$. But for $\overline{b_1{b}_2...b_n}$ to be a palindrome, the equality $b_{i-1}=b_{n+1-(i-1)}$ must hold, which is a contradiction.

If the sum is a $(n+1)$-digit number, its first digit must be 1; let the remaining digits of the sum be $\overline{b_1{b}_2...b_n}$. We will show that for each $i=1,\dots ,n$, either $a_{n+1-i}=a_i=0$ or $a_{n+1-i}+a_i=11$. The statement is obviously true for $i=1$, since $b_n=1$, but $a_n+a_1\ne 1$ due to $a_n>0$, $a_1>0$. Now let $i>1$ and assume that the statement holds for $i-1$. Consider the case $a_{n+1-(i-1)}+a_{i-1}=11$. Depending on whether or not there is a carry in the $(n+1-i)$-th position from the end, $b_{i-1}=2$ or $b_{i-1}=1$. Accordingly, $b_{n-(i-1)}=2$ or $b_{n-(i-1)}=1$, that is, $b_{n+1-i}=2$ or $b_{n+1-i}=1$. Since there is a carry in the $(i-1)$-th position from the end, the last digit of $a_{n+1-i}+a_i$ must be 1 or 0, respectively. Similarly, in the case $a_{n+1-(i-1)}=a_{i-1}=0$, depending on whether or not there is a carry in the $(n+1-i)$-th position from the end, $b_{i-1}=1$ or $b_{i-1}=0$. Accordingly, $b_{n-(i-1)}=1$ or $b_{n-(i-1)}=0$, that is, $b_{n+1-i}=1$ or $b_{n+1-i}=0$. Since there is no carry in the $(i-1)$-th position from the end, the last digit of $a_{n+1-i}+a_i$ is 1 or 0, respectively. In conclusion, we have shown that if there is a carry in the $(n+1-i)$-th position from the end, the last digit of $a_{n+1-i}+a_i$ is 1, and if there is no carry in the $(n+1-i)$-th position from the end, the last digit of $a_{n+1-i}+a_i$ is 0. In the first case, $a_{n+1-i}+a_i=11$, and in the second case, $a_{n+1-i}=a_i=0$. This completes the induction step and proves the desired statement.

All described numbers trivially satisfy the problem's condition. Let's count them. If $n$ is even, the number of $n$-digit numbers for which no carry occurs when adding the number and the number obtained by reversing its digits is $36\cdot 55^{\frac{n-2}{2}}$, because the number of pairs of digits $(a,b)$ whose sum is less than 10 is $8+7+\cdots +1$ or 36, when zero is not allowed (as in the first and last positions), and $10+9+\cdots +1$ or 55, when zero is allowed (as in the other positions). The number of $n$-digit numbers for which the sum of the first and last digits is 11 and the sum of the digits equidistant from the middle is either 0 or 11 is $8\cdot 9^{\frac{n-2}{2}}$. Similarly, if $n$ is odd, the number of $n$-digit numbers for which no carry occurs when adding the number and the number obtained by reversing its digits is $36\cdot 55^{\frac{n-3}{2}}\cdot 5$. The number of $n$-digit numbers for which the sum of the first and last digits is 11 and the sum of the digits equidistant from the middle is either 0 or 11 is $8\cdot 9^{\frac{n-3}{2}}$. Thus, the total number of such numbers is $36\cdot 55^{\frac{n-2}{2}}+8\cdot 9^{\frac{n-2}{2}}$ if $n$ is even and $36\cdot 55^{\frac{n-3}{2}}\cdot 5+8\cdot 9^{\frac{n-3}{2}}$ if $n$ is odd.