How many $5$-digit numbers with distinct digits are divisible by 3 (and generalize)

Question

I'm solving a problem which asks me to find how many 5-digit numbers with distinct digits are there which are also divisible by $3$. I am familiar that there are $9\cdot9\cdot8\cdot7\cdot6=27216$ five-digit numbers with distinct digits. I know that a natural number $n$ is divisible by $3$ iff the digits sum up to a number divisible by $3$. Now, brute-forcing by a computer algorithm, i found that the result is $20928$. However, I am interested, if there is a mathematical solution for this. I know how to find amount of numbers divisible by $4$ or $5$. We just fix some amount on the last two (or last one) digit. But criterion for divisibility by $3$ is very different from those and I have no idea how to start. Eventually, I would like to find a general formula for $n$-digit numbers.

Edit: Equivallently we want to find how many solution does the equation $a+b+c+d+e=3k$ for $a,b,c,d,e\in\{0,1,2,...,9\}$, $a\neq 0$ also $a,b,c,d,e$ are all distinct and $k\in\mathbb{Z}$ (the highest possible $k$ is in this case $k=11$, the smallest being $k=5$)

Edit (2): According to the ideas from the answer. Make $A=\{0,3,6,9\},B=\{1,4,7\}, C=\{2,5,8\}$. Let's go through the cases that in the number $n$ there are $0,1,2,3,4$ digits from $A$.

i) Suppose none of $A$ is in $n$. We can't form a number divisible by three. We have to take 5 numbers, that is $3$ from $A$ and $2$ from $B$ or $2$ from $A$ and $3$ from $B$. None of the expressions $3(3k+1)+2(3k+2)$ and $2(3k+1)+3(3k+2)$ are divisible by three.

ii) Let $1$ digit from $A$ be in $n$. The amount of ways to choose the digit is $5$. Now we are left to choose $4$ digits. The only possible way is to choose $2$ from $A$ and $2$ from $B$. The amount of ways to do this is ${3\choose 2}^2=9$ which together gives $5\times 9$ ways which can be permuted and alltogether $5\times 9\times 5!=5400$ possible ways.

iii) Let $2$ digits from $A$ be in $n$. The amount of ways to choose the digit is ${5\choose 2}=10$. We are left with $3$ digits. Either all of them are from $A$ or all of them are from $B$. That's $2$ possible ways and all together $20$ possible ways which we permute to obtain $20\times 5!=2400$ possible ways.

iv) Let $3$ digits from $A$ be in $n$. The amount of ways to choose the digits from $A$ is ${5\choose 3}=10$. We are to choose $2$ digits. We must take exactly one from $B$ and exactly one from $C$. The amount of ways to do this is ${3\choose 1}^2=9$. Alltogether $9\times 10$ possible ways which we permute to get $90\cdot5!=10800$ possible ways

v) In the last case where all four digits from $A$ are present, there is no way how to make the number divisible by $3$.

Summing this all up gives $5400+2400+10800=18600$ which is less than what my algorithm yielded. We also have to subtract these which begin with $0$. Can anyone spot the mistake? (If i did any?)

Answer 1

The set $S$ of five digit numbers with distinct digits has $27\,216$ elements. Write $S=S'\cup S_0$, whereby $S'$ consists of the numbers $n\in S$ without a $0$ in their decimal expansion, and $S_0$ consists of the numbers $n\in S$ with exactly one $0$ in their decimal expansion. I claim that exactly one third of the numbers in $S$, meaning $9072$, are divisible by $3$.

Proof. Consider the following bijective map $f:\>S\to S$: Given a number $n\in S$, apply the map $$1\mapsto2\mapsto3\mapsto4\mapsto5\mapsto6\mapsto7\mapsto8\mapsto9\mapsto1\>, \qquad 0\mapsto0$$ to its digits. Examples: $f(42937)=53148$, $f(31304)=42405$.

The map $f$ is bijective. Furthermore $f$ adds $2$ mod $3$ to numbers in $S'$, and $1$ mod $3$ to numbers in $S_0$. Now both $S'$ and $S_0$ consist of three parts according to the remainder of $n$ modulo $3$, and $f$ permutes the three parts of $S'$ as well as the three parts of $S_0$. It follows that exactly one third of the numbers in $S'$ and one third of the numbers in $S_0$ is divisible by $3$.

Answer 2

First calculate four-digit numbers with no zeros that are divisible by 3. These are the five-digit numbers that start wlwith 0.

If there are no digits from $A=\{3,6,9\}$ there must be two each from $B=\{1,4,7\}$ and $C=\{2,5,8\}$ so that the sum is a multiple of $3$. Three ways to pick from $\{1,4,7\}$ and three from $\{2,5,8\}$, or nine in all.
If there is one digit from $\{3,6,9\}$, then you need all of $B$ or all of $C$, six possibilities in all.
I think there are $42$ possibilities altogether, which can each be arranged in $24$ ways, to give $1008$ four-digit multiples of $3$ with no zeroes and no repeated digits.

Do the same thing for five-digit numbers.