Problem 872

For $k = 0, 1, 2, 3, 4, 5$ let us denote by $A_k$ the set of all multiples of $3$ less than or equal to $10^6$ whose $10^k$'s digit is $1$, and define $N_k$ to be the number of elements in the set $A_k$. Then the desired answer for the problem is $\sum_{k=0}^5 N_k$.

The set $A_5$ consists of multiples of $3$ lying in between $100000$ and $200000$, and there are $33333$ of those starting with $100002$ and ending with $199998$. Hence $N_5 = 33333$.

Let us now consider $N_k$ for $0 \le k \le 4$. For a number $n$ in the set $A_k$ associate a number $n'$, which is obtained from $n$ by interchanging the $10^k$'s digit of $n$ with the $10^5$'s digit of $n$ (if $n$ has less than $6$ digits, we consider a $6$ digit number by supplying necessary number of $0$'s in upper digits, and define $n'$). Since the sum of the digits of $n'$ obtained in this way is the same as the sum of digits of $n$, we see that $n'$ is a multiple of $3$ and hence belongs to the set $A_5$ as the $10^5$'s digit of $n'$ is $1$. Conversely, by interchanging the $10^5$'s digit and $10^k$'s digit of a number in the set $A_5$, we get a number belonging to the set $A_k$. Thus, we see that there is a one-to-one correspondence between the elements of the sets $A_k$ and $A_5$, and therefore, there are exactly $33333$ elements in the set $A_k$ also for each $k = 0, 1, 2, 3, 4$.

Consequently, the answer we seek is $\sum_{k=0}^5 N_k = 6 \times 33333 = 199998$.