# Counting Techniques Challenge

#### anemone

##### MHB POTW Director
Staff member
How many five digit numbers are divisible by 3 and contain the digit 6?

#### Opalg

##### MHB Oldtimer
Staff member
How many five digit numbers are divisible by 3 and contain the digit 6?
My answer is $\boxed{12504}$.
Altogether, there are $90000$ numbers with five digits. Exactly one-third of these (starting with 10002 and ending with 99999) are divisible by 3. So altogether there are $30000$ five-digit numbers divisible by 3. Now we must subtract all such numbers that contain no 6s.

To count how many five-digit multiples of 3 contain no 6s, look at how many ways there are to choose each of the five digits in the number. There are eight choices for the leading digit (which could be 1,2,3,4,5,7,8 or 9). For each of the second, third and fourth digits, there are nine choices (because we could also have a 0 in those positions). For the final digit, there are three choices. To see why, notice that the sum of the five digits must be a multiple of 3. If the sum of the first four digits is $=1\pmod3$ then the last digit must be 2,5 or 8. If the sum of the first four digits is $=2\pmod3$ then the last digit must be 1,4 or 7. And if the sum of the first four digits is $=0\pmod3$ then the last digit must be 0,3 or 9 (since it can't be 6!). So in every case there are exactly three choices.

Thus altogether there are $8*9^3*3 = 17496$ five-digit multiples of 3 containing no 6s, and subtracting that number from $30000$ we get $12504$ as the answer.

#### anemone

##### MHB POTW Director
Staff member
Well done, Opalg! Your answer is of course correct and for your information, I didn't solve this problem, however, I did find a solution which was very nearly identical to yours, and I never realized that modulo arithmetic could be a tool to solve counting problems like this.

I like your explanation so much and whenever it has come time to read your explanatory posts, you have never failed to enlighten us with your clever step-by-step working and so I thank you for participating and for this brilliant solution! My hat is truly off to you, Mr. Opalg!