Problem 11.4. A positive integer $a$ whose decimal representation has 2006 digits is called "bad" if 3 does not divide any integer formed by three consecutive digits of $a$.

a) Find the number of all bad integers whose digits are equal to 1,2 or 3 .

b) Let $a$ and $b$ be different bad integers such that $a+b$ is also a bad integer. Denote by $k$ the number of positions, where the digits of $a$ and $b$ coincide. Find all possible values of $k$.

Emil Kolev
11.4. a) Let $n>1$ and $a=\overline{a_{1} a_{2} \ldots a_{n}}$ be a bad integer with digits 1,2 and 3. Since 3 divides exactly one of the integers $\overline{a_{n-1} a_{n} 1}, \overline{a_{n-1} a_{n} 2}$ and $\overline{a_{n-1} a_{n} 3}$, then exactly two of them are bad. It follows that adding 1,2 or 3 to $a$ one obtains exactly two bad integers with $n+1$ digits. Since the number of the two-digit integers whose decimal representations contain only the digits 1,2 or 3 equals 9 , the answer of a) is $9 \cdot 2^{2004}$.
b) The integers $122122 \ldots 12212$ and $233233 \ldots 23323$ are bad and their sum $355355 \ldots 35535$ is also a bad integer. Thus 0 is one of the possible values of $k$.

Let now $a=\overline{a_{1} a_{2} \ldots a_{n}}$ and $b=\overline{b_{1} b_{2} \ldots b_{n}}$ be different bad integers and suppose that their sum is also a bad integer. Then 3 does not divide $a_{i}+a_{i+1}+$ $a_{i+2}, b_{i}+b_{i+1}+b_{i+2}$ and $a_{i}+a_{i+1}+a_{i+2}+b_{i}+b_{i+1}+b_{i+2}$. This means that $a_{i}+a_{i+1}+a_{i+2} \equiv b_{i}+b_{i+1}+b_{i+2} \equiv 1,2(\bmod 3)$. Assume that two of the digits $a_{i}, a_{i+1}, a_{i+2}$ coincide with the respective digits $b_{i}, b_{i+1}, b_{i+2}$. It follows from above that the third digits also coincide. Continuing in the same way, we conclude that $a=b$, a contradiction.

So, among any three consecutive digits of $a$, at most one coincides with the respective digit of $b$. On the other hand, if $a_{i}=b_{i}$, then $a_{i+3}=b_{i+3}$ (and analogously $a_{i-3}=b_{i-3}$ ). Indeed $a_{i}+a_{i+1}+a_{i+2} \equiv b_{i}+b_{i+1}+b_{i+2}$ $(\bmod 3)$ implies that $a_{i+1}+a_{i+2} \equiv b_{i+1}+b_{i+2}(\bmod 3)$. If $a_{i+3} \neq b_{i+3}$ : then $a_{i}+a_{i+1}+a_{i+2} \equiv b_{i}+b_{i+1}+b_{i+2}(\bmod 3)$ which is impossible.

Thus, if $k>0$, then among any three consecutive digits of $a$ exactly one coincides with the respective digit of $b$. It follows that $k=669$ or $k=668$.