Determine the number of numbers we can make between $1000$ and $9999$
of $4$ different digits without $0$. How many of those numbers are
divisible by $3$?
To calculate how many numbers there are between $1000$ and $9999$ of $4$ different digits without $0$
, we calculate $9*8*7*6=3024$.
To calculate how many of those numbers are divisible by $3$ , I tried to combine that the sum of the digits must be divisible by $3$ and the stars and bars theorem.
Since we have 4 different digits the maximum sum of the digits is $9+8+7+6=30$ and the minimum is $1+2+3+4=10$.
The possible sums of the digits for which the number is divisible by $3$ are thus $12,15,18,21,24,27$ and $30$.
But with the stars and bars I didn't really know how to do its because we have to have 4 different digits and no zeros.
The solution my book gave was simply $42*4!$, so I think I'm on the wrong track, but I have no idea how they got to their solution.
Any nudge in the right direction is appreciated 🙂
EDIT
I figured out the solution from my book.
If we take the numbers 1 to 9 we can divide them in 3 sets mod 3.
0 mod 3 would be the numbers {3,6,9}
1 mod 3 would be the numbers {1,4,7}
2 mod 3 would be the numbers {2,5,8}
Now we can use that the sum of the 4 digits must be $0$.
We can take 1 number from the 0 mod 3 set and 3 from the 1 mod 3 set, for example 3147. There are 4! ways to use the numbers {3,4,1,7}. There are 3 ways to select 1 number from 0 mod 3 set and 3 from the 1 mod 3 set.
Other ways to get a sum of 3:
2 numbers from the 0 mod 3 + 1 number from 2 mod 3+ 1 number from 1 mod 3. There are 3*3*3=27 ways to do this.
3 numbers from 2 mod 3+1 from 0 mod 3 . There are 3 ways to do this.
2 numbers from 1 mod 3 + 2 numbers from 2 mod 3. There are 3*3= 9 ways to do this.
So there are 3+27+3+9=42 ways to get a 4 digit number with sum equal to 3, and we have 4! ways to rearrange those numbers, so 42*4! numbers between 1000 and 9999 comply with all the requirements.
Best Answer
There are $3024$ such numbers in total, as as you say. And exactly one third of these numbers is divisible by $3$.
We can see this by grouping them into three sets $S_0,S_1,$ and $S_2$, according to the sum of their digits modulo $3$. Given any element of $S_0$, we can construct a unique element of $S_1$ simply by adding $1$ to each digit (with $9$ wrapping around to $1$). And we can construct a unique element of $S_2$ in the same way by adding $2$ to each digit.
So these three sets are all the same size, which is $3024/3=1008$.