5digit numbers divisble by 6

**markjonathan** · September 2nd 2011, 08:04 AM

Hello guys, I need some help...

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

Thanks in advance

**Soroban** · September 2nd 2011, 08:48 AM

Hello, markjonathan!

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).

. . $\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?

**emakarov** · September 2nd 2011, 09:08 AM

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

$\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 $n$ and column $s$ is the number of different tuples $\langle a_1,\dots,a_n\rangle$ such that $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 $x_{n,s}$ is the value in row $n$ , column $s$ , then $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 $x_{4,4}+x_{4,7}+x_{4,10}$ . I got the same answer as Soroban.

Thread: 5digit numbers divisble by 6

LinkBack

Thread Tools

Display

5digit numbers divisble by 6

Re: 5digit numbers divisble by 6

Re: 5digit numbers divisble by 6

Similar Math Help Forum Discussions

n^3+n=m^4 proving n has to be even and divisble by 16

Random choice of numbers from series, probability the numbers are equal?

prove that n^3 + 5n is divisble by 6 using induction

Finding real numbers in equations containing complex numbers

In a new lotto game, you must choose six numbers from the numbers 1 to 25. Six winn

Search Tags