1. Let $n$ be the sum of all ten-digit numbers that have each of the digits $0,1, \ldots, 9$ in their decimal representation. Determine the remainder when $n$ is divided by seventy-seven.
SOLUTION. First, we will find the value of the number $n$, then it will be easy to determine its remainder when divided by 77. We will not directly add the ten-digit numbers described in the problem. The desired sum can be more easily found by determining how many times each digit appears in all the addends at the units, tens, hundreds, etc. places. We will then determine the "contribution" of each digit to the total sum $n$.

If the digit 1 is in the units place, then we can arrange the remaining nine digits in the remaining nine places in any order, except that we cannot place the digit 0 in the first place. We can place one of the eight different digits (any except 0) in the first place, one of the eight different digits (any except the one placed in the first place) in the second place, one of the seven different digits (any except the digits in the first two places) in the third place, etc. The digit 1 is therefore in the units place $8 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1=8 \cdot 8$ ! times. ${ }^{1}$

By the same reasoning, we find that the digit 1 appears $8 \cdot 8$ ! times in the tens, hundreds, thousands, etc. places. It appears 9 ! times only in the first position, because then we can arrange the remaining nine digits in the remaining nine places in any order - there is no restriction for the digit 0.

The contribution of the digit 1 to the total sum is therefore

$$
\begin{gathered}
8 \cdot 8 !+8 \cdot 8 ! \cdot 10+8 \cdot 8 ! \cdot 100+\ldots+8 \cdot 8 ! \cdot 10^{8}+9 ! \cdot 10^{9}= \\
\quad=8 \cdot 8 ! \cdot 111111111+9 \cdot 8 ! \cdot 10^{9}=8 ! \cdot 9888888888 .
\end{gathered}
$$

The digit 2, of course, appears in all the addends in the various places as many times as the digit 1, so its contribution to the total sum is double. The contribution of the digit 3 is triple, the contribution of the digit 4 is quadruple, etc. The number of occurrences of the digit 0 in the various places is different from the other digits, but we do not need to determine it, because the contribution of the digit 0 to the sum is zero. Altogether, we have

$$
n=8 ! \cdot 9888888888 \cdot(1+2+\ldots+9)=45 \cdot 8 ! \cdot 9888888888 .
$$

We could now determine the desired remainder by calculating the value of $n$ and dividing by 77. However, we will avoid the tedious multiplication and division of large numbers. From the expression (1), we see that $n$ is divisible by seven (because the factor 8! is a multiple of seven). Since $77=7 \cdot 11$, the remainder of the number $n$ when divided by seventy-seven must also be a multiple of seven.

We will still determine the remainder of the number $n$ when divided by eleven. Trivially, $45 \equiv 1(\bmod 11)$ and it is easy to calculate that $8 !=40320 \equiv 5(\bmod 11)$. We can speed up the determination of the remainder of the number 9888888888 using a known statement: A number $\mathrm{s}$ with the decimal representation $\overline{a_{k} a_{k-1} \ldots a_{1} a_{0}}$ gives the same remainder when divided by eleven as the number $a_{0}-a_{1}+a_{2}-\ldots+(-1)^{k} a_{k}$. We thus get

$$
9888888888 \equiv 8-8+8-8+\ldots+8-9=-1 \equiv 10(\bmod 11)
$$

Overall, we get

$$
n=45 \cdot 8 ! \cdot 9888888888 \equiv 1 \cdot 5 \cdot 10=50 \equiv 6(\bmod 11)
$$

(we used the fact that the product of factors gives the same remainder as the product of their remainders).

The remainder when the number $n$ is divided by seventy-seven is therefore the number from the set $\{6,17,28,39,50, 61,72\}$ that is divisible by seven, i.e., the number 28.