A five digit number $\overline{a_1 a_2 a_3 a_4 a_5}$ is said to satisfy property P if $a_i \in \{1,2,3,4,5,6,7 \} \quad 1\leq \forall i \leq 5$.
How many five digit numbers satisfy P such that $k=a_1+a_2+a_3+a_4+a_5$ is divisible by:
(a) $3$
(b) $2$
(c) $4$
(Separate sub questions).
The first method(which is really lengthy but worked) is separating each $a_i$ into remainders when divided by $3,2,4$ respectively and doing all lot of case work for the digital sum divisibility condition.
The final answer is of a very nice form:
(a)$\frac{7^5-1}{3}$
(b)$\frac{7^5-1}{2}$
(c)$\frac{7^5-3}{4}$
So I thought there should be a better approach. Although the number of five digits numbers leaving a particular remainder when divided by $3$ or $2$ or $4$ won't be equal, as the groups which each $a_i$ is divided into based on remainder(this isn't needed for the question though), are of unequal sizes(for all three cases).
But given the answer form, I wondered if it is true that when the digital sum k is divided by a number, then they are equally distributed among all the possible remainders.
For example for case (a), we can divide $k \in [5,35]$ into groups of $3$ based on remainder when divided by $3$, then the groups are of sizes $10$ ($0 \mod 3$), $10$ ($1 \mod 3$), $11$ ($2 \mod 3$). The extra number in the last group ($2 \mod 3$) is $5$, and only one five number has $k=5$.
So is it correct to say that the from the total $7^5$ possible numbers, if we subtract this extra number to give a total $7^5-1$ numbers, these are equally divided into the three groups to give a total number of $\frac{7^5-1}{3}$ numbers(the answer)? Similar reasoning for case (b),(c).
Is there any other way to solve this question? I briefly also tried using multinomial theorem and got that the required answer for case(a) is the sum of coefficients of $x^{3n}, n=0,1,2,3,\ldots$ in the expansion of $(x+x^2+\ldots+x^7)^5$ but I could make little to no progress in evaluating this.
Best Answer
You should consider these to be strings of digits as we do not use the properties of the number, just the sum of the digits. You can write a set of coupled recurrences for the number of strings that sum to the number with each remainder. For $n$ digits there is a total of $7^n$ strings. For the $\bmod 4$ case, let $a(n)$ be the number of strings with a remainder of $0$, $b(n)$ with remainder $1$, c(n) with remainder $2$ and $d(n)$ with remainder $3$. We have $$a(n)=a(n-1)+2b(n-1)+2c(n-1)+2d(n-1)=2\cdot 7^{n-1}-a(n-1)\\ a(1)=1$$ and similarly for the others except that the sequence starts with $2$ as there are $2$ digits of each remainder except $0$ The strings will be close to equally distributed so if you compute it in a spreadsheet and subtract $a(n)-\frac 14\cdot7^n$ you see it alternates $\pm \frac 34$ and we get $$a(n)=\frac 14\cdot \left(7^n+(-1)^n\cdot 3\right)$$ The rest will be $$b,c,d(n)=\frac 14\cdot \left(7^n-(-1)^n\right)$$