3. A natural number will be called magical if and only if it can be expressed as the sum of two three-digit numbers written with the same digits but in reverse order. For example, the number 1413 is magical because $1413=756+657$; the smallest magical number is 202.

a) Determine the number of all magical numbers.

b) Show that the sum of all magical numbers is equal to 187000.
SOLUTION. Taking the number 1413 as an example, we see that it is not always easy to tell whether a given three- or four-digit number is magical or not. Therefore, let's first look at how a magical number $x$ can be expressed using the digits of those three-digit numbers $\overline{a b c}$ and $\overline{c b a}$, which are their sum:

$$
x=\overline{a b c}+\overline{c b a}=(100 a+10 b+c)+(100 c+10 b+a)=101(a+c)+20 b .
$$

We see that the number $x$ is determined by the digits $a, b, c$ in such a way that it depends only on $b$ and on the sum $a+c$. This means that different triples of digits $a, b, c$ can determine the same magical number $x$ (we do not mean triples differing only by the mutual exchange of digits $a$ and $c$). For example, if $a+c=14$ and $b=9$, we find three different representations of the magical number 1594:

$$
1594=599+995=698+896=797+797 .
$$

Are there any other "magical" representations of the number 1594? It all depends on whether the values of the sum of the digits $s=a+c$ and the digit $b$ are uniquely determined by the equation $1594=101 s+20 b$. From the equation, we immediately see that the number $s$ ends in the digit 4, so $s=4$ or $s=14$ (other values of the sum $s=a+c$ are not achievable by the digits $a, c$). While the value $s=14$ corresponds (as we well know) to the value $b=9$, for $s=4$ we get the equation $1594=404+20 b$, which has no integer solution.

Encouraged by the above example, we will try to determine the number of magical numbers as the number of numbers of the form $x=101 s+20 b$, where the number $s$ (equal to the sum of the digits $a$ and $c$, which are non-zero) runs through the set $\{2,3,4, \ldots, 18\}$, while the digit $b$ runs through (independently of the sum $s$) the set $\{0,1,2, \ldots, 9\}$. Since the number $s$ takes 17 different values and the number $b$ takes 10 different values, the number of all pairs $(s, b)$ that we can substitute into the formula $x=101 s+20 b$ is equal to the number $17 \cdot 10=170$. If we now show that by substituting any two different pairs $\left(s_{1}, b_{1}\right)$ and $\left(s_{2}, b_{2}\right)$ we get two different magical numbers

$$
x_{1}=101 s_{1}+20 b_{1} \quad \text { and } \quad x_{2}=101 s_{2}+20 b_{2} \text {, }
$$

it will mean that the number of all values of $x$ (i.e., the number of all magical numbers) is also equal to the number 170.

Suppose that for some pairs $\left(s_{1}, b_{1}\right)$ and $\left(s_{2}, b_{2}\right)$ we have $x_{1}=x_{2}$. The equation $101 s_{1}+$ $+20 b_{1}=101 s_{2}+20 b_{2}$ can be rearranged to the form $101\left(s_{1}-s_{2}\right)=20\left(b_{2}-b_{1}\right)$, from which, due to the coprimality of the numbers 20 and 101, it follows that the number $b_{2}-b_{1}$ is a multiple of the number 101. It must be a zero multiple, since $\left|b_{2}-b_{1}\right| \leqq 9$ ( $b_{1}$ and $b_{2}$ are digits!). Therefore, $b_{2}-b_{1}=0$, and thus also $s_{1}-s_{2}=0$, which together means that the pairs $\left(s_{1}, b_{1}\right)$ and $\left(s_{2}, b_{2}\right)$ are the same. Only in this case is the equality $x_{1}=x_{2}$ possible.

The sum of all magical numbers (i.e., numbers of the form $x=101 s+20 b)$ can be conveniently determined by first arranging the numbers into a rectangular scheme (according to the same values of $s$ in rows and according to the same values of $b$ in columns)

$$
\begin{array}{ccccc}
101 \cdot 2+20 \cdot 0 & 101 \cdot 2+20 \cdot 1 & 101 \cdot 2+20 \cdot 2 & \ldots & 101 \cdot 2+20 \cdot 9 \\
101 \cdot 3+20 \cdot 0 & 101 \cdot 3+20 \cdot 1 & 101 \cdot 3+20 \cdot 2 & \ldots & 101 \cdot 3+20 \cdot 9 \\
101 \cdot 4+20 \cdot 0 & 101 \cdot 4+20 \cdot 1 & 101 \cdot 4+20 \cdot 2 & \ldots & 101 \cdot 4+20 \cdot 9 \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
101 \cdot 17+20 \cdot 0 & 101 \cdot 17+20 \cdot 1 & 101 \cdot 17+20 \cdot 2 & \ldots & 101 \cdot 17+20 \cdot 9 \\
101 \cdot 18+20 \cdot 0 & 101 \cdot 18+20 \cdot 1 & 101 \cdot 18+20 \cdot 2 & \ldots & 101 \cdot 18+20 \cdot 9
\end{array}
$$

and then summing the numbers either by columns or by rows. We will opt for summing by columns, taking into account how much the numbers in the column under consideration differ from the corresponding numbers in the first column. The sum of the numbers in the first column is

$$
101 \cdot(2+3+\ldots+18)=101 \cdot 170
$$

in the second column, the sum is $101 \cdot 170+17 \cdot 20 \cdot 1$, in the third $101 \cdot 170+17 \cdot 20 \cdot 2$, and so on up to the last (tenth) column, where the sum of the numbers is $101 \cdot 170+17 \cdot 20 \cdot 9$. The sum of all magical numbers is therefore equal to

$$
10 \cdot 101 \cdot 170+17 \cdot 20 \cdot(1+2+\ldots+9)=187000 .
$$

GUIDING PROBLEMS: