Results 1 to 3 of 3

Math Help - 5digit numbers divisble by 6

  1. #1
    Newbie
    Joined
    Sep 2011
    Posts
    2

    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?

    Thanks in advance
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,865
    Thanks
    744

    Re: 5digit numbers divisble by 6

    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?

    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

    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

    \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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. n^3+n=m^4 proving n has to be even and divisble by 16
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 22nd 2011, 03:45 PM
  2. Replies: 1
    Last Post: August 29th 2011, 03:18 AM
  3. prove that n^3 + 5n is divisble by 6 using induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: January 18th 2011, 02:01 PM
  4. Replies: 1
    Last Post: September 27th 2010, 04:14 PM
  5. Replies: 3
    Last Post: April 10th 2008, 06:58 PM

Search Tags


/mathhelpforum @mathhelpforum