How many 5 digits numbers such that when the sum of digit divided by 4 leaves remainder 2.
Example:-
Consider a 5 digit number-
$(x1,x2,x3,x4,x5)$
Then $(x1+x2+x3+x4+x5)$ must be of form $(4n+2)$
I tried this
(x+x²+x³…+x^9)(1+x+x²+x³….+x^9)⁴
In this sum of coefficient of x^(2,6,10,14….42)
But this involve lot of calculation.!
Please some one provide me something different and smarter solution.
Best Answer
Call digits $0$ and $1$ small, and digits $2-9$ large.
Given $n\ge 1$, we divide the $n$-digit numbers into two sets: $S$, which contains all numbers consisting entirely of the small digits $0$ and $1$; and $L$, which contains all other numbers. Note that:
Now, if $c$ and $d$ are large digits, then the number of numbers whose first large digit is $c$ is equal to the number of numbers whose first large digit is $d$. And because the large digits are evenly distributed modulo $4$, this means that the digit sums of the numbers in $L$ are also evenly distributed modulo $4$. So the number of numbers in $L$ with a given digit sum modulo $4$ is $|L|/4$.
This just leaves $S$. But this is easy: the number of numbers in $S$ with digit sum $k$ is the number of ways of choosing $k-1$ positions for the $1$'s (given that the first digit has to be $1$). This is the binomial coefficient $\binom{n-1}{k-1}$.
Thus we see that the number of $n$-digit numbers with a digit sum equal to $m$ mod $4$ is equal to $|L|/4+\sum_k\binom{n-1}{k-1}$, where the sum is taken over all $k$ with $1\le k\le n$ and $k\equiv m$ mod $4$.
Here is a table of the number of $n$-digit numbers with a given digit sum modulo $4$, for $n=1$ to $6$: $$ \begin{array}{c|lcr} n & |L|/4 & 0\bmod 4 & 1\bmod 4 & 2\bmod 4 & 3\bmod 4 \\ \hline 1 & 2 & 2 & 3 & 2 & 2\\ 2 & 22 & 22 & 23 & 23 & 22\\ 3 & 224 & 224 & 225 &226 &225\\ 4 & 2248 & 2249 & 2249 & 2251 & 2251\\ 5 & 22496 & 22500 & 22498 & \color{red}{22500} & 22502\\ 6 & 224992 & 225002 & 224998 & 224998 & 225002\\ \end{array} $$