
1. Let $S_{n}$ denotes the sum of all n-digit numbers, which contain only digits 1,2 , 3, at least once each. Find all integers $n \geqslant 3$ such that $S_{n}$ is divisible by 7 .

(Pavel Novotný)


Solution. Similarly as in Problem 1 of the take-home part, we compute the sum by summing up all the contributions by all digits. The number of occurrences of any of the digits on an arbitrary but given place in the number is $k=3^{n-1}-2 \cdot 2^{n-1}+1$ (we fix one position, if all the others were arbitrary, we would get $3^{n}$ occurrences, but we have to subtract numbers consisting only of two or one digit). Then the contribution $p$ of the digit 1 to the sum is

$$
p=k+10 k+100 k+\cdots+10^{n-1} k=\left(1+10+100+\cdots+10^{n-1}\right) k=\frac{10^{n}-1}{9} k .
$$

The contributions of the digit 2 and 3 are obviously $2 p$ and $3 p$, thus

$$
S_{n}=p+2 p+3 p=6 p=6 \cdot \frac{10^{n}-1}{9} k=\frac{2}{3}\left(10^{n}-1\right)\left(3^{n-1}-2^{n}+1\right) .
$$

$S_{n}$ is divisible by 7 iff at least one of the factors $10^{n}-1,3^{n-1}-2^{n}+1$ is. The following table lists the factors modulo 7 for a few small integers:

| $n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| ---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| $10^{n}-1$ | 9 | 99 | 999 | 9999 | 99999 | 999999 | $\ldots$ |  |
| modulo 7 | 2 | 1 | 5 | 3 | 4 | 0 | 2 | 1 |
| $3^{n-1}-2^{n}+1$ | 0 | 0 | 2 | 12 | 50 | 180 | 602 | 1932 |
| modulo 7 | 0 | 0 | 2 | 5 | 1 | 5 | 0 | 0 |

Both sequences modulo 7 are periodic with the period $6\left(10^{n}\right.$ modulo 7 is periodic with the period 6 , so is $10^{n}-1 ; 3^{n}$ modulo 7 is periodic with the period 6 and $2^{n}$ modulo 7 has period 3 , thus $3^{n-1}-2^{n}+1$ has period 6 ) and $10^{n}-1$ is divisible by 7 for $n=6 k, 3^{n-1}-2^{n}+1$ is a multiple of 7 for $n=6 k+1$ or $n=6 k+2$.

Conclusion. All solutions of the problem are integers of the form $6 m, 6 m+1$, and $6 m+2$ for any positive integer $m$.
