"The total number of possible combination of 5 digits numbers formed from the digits(0,1,2,3,4,5,6,7,8,9) which are divisible by 3?"
This was the question given to me by my mathematics teacher during out permutation and combination lessons;I was able to solve this with ease but later I was thought of modifing the problem a little bit to
"The total number of possible combination of 5 digits numbers formed from the digits(0,1,2,3,4,5,6,7,8,9) which are divisible by 3 without repetation of any digits? eg 12345 not 33120"
I asked my teacher about the solution of the problem because i was unable to solve it with certain accuracy, he was unable to give me a satisfactory answer.
Can anyone help me in solving this problem
thank you.
Best Answer
Update
Among the $10$ digits there are $4$ having remainder $0$ mod $3$, and $3$ each having remainder $1$ or $2$ mod $3$. We have to select $x_0$, $x_1$, $x_2$ of these digits, such that $$x_0+x_1+x_2=5,\qquad x_1-x_2=0\quad {\rm mod}\ 3\ .\tag{1}$$
We can partition $5$ into three nonnegative parts in the following $5$ ways: $$p_1:\ 5+0+0,\quad p_2:\ 4+1+0,\quad p_3:\ 3+2+0,\quad p_4:\ 3+1+1,\quad p_5:\ 2+2+1\ .$$ The first and the second of these cannot be used. Then $p_3$ together with $(1)$ leads to the solutions $(x_0,x_1,x_2)=(2,3,0)$ and $(x_0,x_1,x_2)=(2,0,3)$. For $p_4$ we obtain $(x_0,x_1,x_2)=(3,1,1)$, and for $p_5$ we obtain $(x_0,x_1,x_2)=(1,2,2)$.
It follows that we can select the five digits in $$2{4\choose2}{3\choose3}+{4\choose 3}{3\choose1}{3\choose1}+{4\choose 1}{3\choose2}{3\choose2}=84\tag{2}$$ ways. Multiply this by $5!=120$ to account for their arrangement, and obtain $10\,080$.
In a comment later on the OP has excluded the strings beginning with $0$. In order to account for this we first compute the admissible selections of five digits containing no $0$. To this end it suffices to replace $4$ by $3$ in $(2)$: $$2{3\choose2}{3\choose3}+{3\choose 3}{3\choose1}{3\choose1}+{3\choose 1}{3\choose2}{3\choose2}=42\ .$$ Therefore $84-42=42$ admissible selections of five digits contain a zero, and these give rise to $42\cdot{5!\over5}=1008$ strings beginning with a $0$. Subtract these from $10\,080$, and obtain $9072$ as final result.