3. Consider all possible 100-digit natural numbers, in the decimal representation of which only the digits 1 and 2 appear. How many of them are divisible by 3?
Solution: Each 100-digit natural number can be obtained by appending two digits to the right of a 98-digit number. Let $x$ be some 98-digit number. We will examine which two digits (each equal to 1 or 2) need to be appended to the number $x$ so that the resulting 100-digit number is divisible by 3. We will use the fact that the remainder of the division of a natural number by 3 is equal to the remainder of the division of the sum of its digits by 3. Let the number $x$ give a remainder $m$ when divided by 3. Then

## Interregional Olympiad for Schoolchildren Based on Departmental Educational Organizations in Mathematics

- if $m=0$, then append 12 or 21;
- if $m=1$, then append 11;
- if $m=2$, then append 22;

Thus, from each 98-digit number that is divisible by 3, two 100-digit numbers divisible by 3 can be obtained. Each 98-digit number that is not divisible by 3 generates only one number divisible by 3.

![](https://cdn.mathpix.com/cropped/2024_05_06_1b63bab14148baefe1f1g-2.jpg?height=52&width=1833&top_left_y=502&top_left_x=114)
We will denote by $A_{n}$ the number of $n$-digit numbers divisible by 3. Then the number of 100-digit numbers divisible by 3 can be found using the formula $A_{100}=2 A_{98}+\left(2^{98}-A_{98}\right)=2^{98}+A_{98}$. Thus, the following relationships are valid:

$$
\begin{gathered}
A_{100}=2^{98}+A_{98} \\
A_{98}=2^{96}+A_{96} \\
\ldots \\
A_{6}=2^{4}+A_{4} \\
A_{4}=2^{2}+A_{2}
\end{gathered}
$$

By summing these equations (the values $A_{4}, \ldots, A_{98}$ cancel out), we get $A_{100}=A_{2}+2^{2}+$ $2^{4}+\cdots+2^{98}$. It remains to sum the geometric progression and note that $A_{2}=2$. Then $A_{100}=2+\frac{4^{50}-4}{3}=\frac{4^{50}+2}{3}$.

Answer: $\frac{4^{50}+2}{3}$.