My textbook has the same problem, except for 5-digit numbers the sum of whose digits is a multiple of 5. The general approach is:
Select the first 4 digits. Number of possible ways of doing this = $9\times 10 \times 10 \times 10$ since the ten thousands-place digit cannot be zero. The sum of these 4 digits is $5k$, $5k+1$, $5k+2$, $5k+3$, or $5k+4$. If it's $5k$, the last digit may only be $0$ or $5$. Sum is $5k+1 \implies$ last digit is $4$ or $9$, and so on. In each case, there are only $2$ possible last digits.
Therefore the total number of such 5-digit numbers is $9\times 10 \times 10 \times 10 \times 2 = 18000$.
When we apply this approach to the "sum of digits is a multiple of 4" problem, we get,
Sum of first 4 digits is $4k \implies$ last digit is $0$, $4$, or $8$.
Sum of first 4 digits is $4k+1 \implies$ last digit is $3$ or $7$.
Sum of first 4 digits is $4k+2 \implies$ last digit is $2$ or $6$.
Sum of first 4 digits is $4k+3 \implies$ last digit is $1$, $5$ or $9$.
In two of these cases, we get three possible last digits and in the other two, we get two possible last digits. Our general approach clearly breaks down here. One way to go around this would be to ask ourselves, "how many ways can we select four digits such their sum is $4k$ or $4k+3$", and multiply that number by 3; repeat for $4k+2$ and $4k+1$ but multiply by 2. Add both these numbers to get the answer.
This seems too long. Is there a simpler way to do this?
Best Answer
Let $S$ be the set of numbers where at least one digit is in the range $\{1,\dots,8\}$. I claim that exactly one fourth of the numbers in $S$ have a digit sum which is a multiple of $4$. To do this, we will partition $S$ into groups of four, where the numbers in each group have different remainders modulo $4$.
Let $S_1$ be the set of numbers in $S$ whose first digit is in $\{1,\dots,8\}$, and let $x$ be some number in $S_1$. If the first digit of $x$ is in $\{1,2,3,4\}$, the group containing $x$ is made by changing that digit to the other numbers in $\{1,2,3,4\}$. For example, the group containing $34682$ would be $\{14682, 24682, 34682, 44682\}$. You do the corresponding thing if the first digit is in $\{5,6,7,8\}$.
But what do we do if the first digit is $0$ or $9$? You then consider $S_2$, the set of numbers whose first digit is $0$ or $9$, and whose second digit is in $\{1,\dots,8\}$, and do the same procedure in the first bullet to the second digit.
Then, you let $S_3$ be the set of numbers each of whose first two digits are $0$ or $9$, and whose third digit is in $\{1,\dots,8\}$, and do the same thing. Same with $S_4$.
Since $S$ is the non-overlapping union of $S_1,S_2,S_3$ and $S_4$, we have partitioned $S$ into groups of four as desired. Therefore, we need to count the number of numbers in $S$ and divide by $4$ to find the number of desired numbers in $S$. To count $S$, use complementary counting.
What about the numbers outside $S$? There are only $16$ of these, and you can count the number of these whose digit sum is a multiple of four directly.