# 5digit numbers divisble by 6

• Sep 2nd 2011, 08:04 AM
markjonathan
5digit numbers divisble by 6
Hello guys, I need some help...

How many 5-digit numbers that consist only of digits 1, 2 and 3 are divisible by 6?

• Sep 2nd 2011, 08:48 AM
Soroban
Re: 5digit numbers divisble by 6
Hello, markjonathan!

Quote:

How many 5-digit numbers that consist only of digits 1, 2 and 3 are divisible by 6?

There is no neat formula for this problem.
I had to use brute-force Listing.

To be divisible by 2, the number must be even; it must end with 2.
To be divisible by 3, the digit-sum of the number must be a multiple of 3.

I found only five cases (and their permutations).

. . $\displaystyle \begin{array}{ccc}\text{Digits} & \text{Permuations} \\ \hline 1,1,1,1,2 & 1 \\ 1,2,2,2,2 & 4 \\ 1,1,2,3,2 & 12 \\ 1,3,3,3,2 & 4 \\ 2,2,3,3,2 & 6 \\ \hline & 27 \end{array}$

Did I miss any?

• Sep 2nd 2011, 09:08 AM
emakarov
Re: 5digit numbers divisble by 6
The last digit must be 2 (why?). The sum of the first four digits must give the remainder 1 when divided by 3 (why?). Since that sum is between 4 and 12, it has to be 4, 7, or 10.

We need to find the number of tuples <a1, a2, a3, a4> such that a1 + a2 + a3 + a4 = 4, or 7, or 10. If there were no restrictions on the maximum of the tuple elements, then we could use the Stars and bars theorem. However, in this case it is probably easier to calculate the number by hand.

One way to do this is using the methods of dynamic programming. Consider the following table

$\displaystyle \begin{array}{c|c|c|c|c|c|c|c|c|c|c|}& 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\\hline n = 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\hline n = 2 & 0 & 1 & 2 & & & & & & &\\\hline n = 3 & 0 & 0 & 1 & 3 & & & & & &\\\hline n = 4 & 0 & 0 & 0 & 1 & & & & & &\\\end{array}$

Columns correspond to sums and rows correspond to the numbers of terms in sums. The cell in row $\displaystyle n$ and column $\displaystyle s$ is the number of different tuples $\displaystyle \langle a_1,\dots,a_n\rangle$ such that $\displaystyle a_1+\dots+a_n=s$. Some of the cells are easy to fill. Note that each value in the middle of the table is the sum of three values in the row above and immediately to the left, i.e., if $\displaystyle x_{n,s}$ is the value in row $\displaystyle n$, column $\displaystyle s$, then $\displaystyle x_{n+1,s}=x_{n,s-1}+x_{n,s-2}+x_{n,s-3}$ (why?). This allows filling the table in a systematic way. The answer to the problem is $\displaystyle x_{4,4}+x_{4,7}+x_{4,10}$. I got the same answer as Soroban.