Results 1 to 4 of 4

Math Help - Combinatorics

  1. #1
    Senior Member
    Joined
    Nov 2007
    Posts
    329

    Combinatorics

    How many different ten-digit number can be created using only 2s and 0s which is divisible by 4 and doesn't contain two neighbouring 0s?

    I know that the last two digits as a number have to be a multiple of 4 so the number is: \overline{\dots 20}.

    And how can I count the numbers not containing neighbouring 0s?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Quote Originally Posted by james_bond View Post
    How many different ten-digit number can be created using only 2s and 0s which is divisible by 4 and doesn't contain two neighbouring 0s?

    I know that the last two digits as a number have to be a multiple of 4 so the number is: \overline{\dots 20}.

    And how can I count the numbers not containing neighbouring 0s?

    I have not gone over it carefully since I have to go now, but here is a guess.

    Generalise it for: \mathop {a_n ...a_3 20}\limits^{\_\_\_\_\_\_\_\_\_\_\_\_} show that the number of possibilities is [tex] f_n [/Math] (nth fibonacci number) Try using induction (draw a diagram)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1
    Quote Originally Posted by james_bond View Post
    How many different ten-digit number can be created using only 2s and 0s which is divisible by 4 and doesn't contain two neighboring 0s? I know that the last two digits as a number have to be a multiple of 4 so the number is: \overline{\dots 20}.
    I assume that 0202020220 will count as such a ten-digit number even though it begins with a zero.
    \sum\limits_{k = 0}^4 {\binom{9-k}{k}}=55 is the answer.
    In the first eight places in the number we can have anywhere from no 0’s(k=0) to at most four 0’s(k=4).
    Then there will be 8-k 2’s creating 9-k to place and separate the 0’s.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,715
    Thanks
    633
    Hello, James!

    How many different ten-digit number can be created using only 2s and 0s
    which is divisible by 4 and doesn't contain two neighbouring 0s?

    I know that the last two digits as a number have to be a multiple of 4
    . . so the number ends in: . \hdots 20

    And how can I count the numbers not containing neighbouring 0s?
    I assume that the leading digit cannot be zero.

    So we have: . 2\:\_\:\_\:\_\;\_\;\_\;\_\;\_\;2\;0
    . . Hence, we want 7-digit numbers with non-adjacent 0s.


    I couldn't find a way to think through this task, so I drew a tree diagram.
    . . And here's what I found . . .

    . . \begin{array}{c|c}\text{no. of digits} & \text{no. of ways} \\ \hline<br />
1 & 2 \\ 2 & 3 \\ 3 & 5 \\ 4 & 8 \\ 5 & 13 \\ \vdots & \vdots \end{array}\quad\hdots\quad\text{These are Fibonacci numbers!}

    Hence, there are 34 seven-digit numbers with non-adjacent 0s.


    Therefore, the answer is: . {\bf{\color{blue}34}}


    ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

    Plato allowed a leading zero, so his result is the next Fibonacci number, 55.

    I love your solution, Plato!

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Combinatorics.
    Posted in the Discrete Math Forum
    Replies: 16
    Last Post: July 20th 2010, 02:29 AM
  2. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 18th 2010, 08:14 PM
  3. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 3rd 2010, 05:24 PM
  4. combinatorics
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 1st 2010, 10:53 PM
  5. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 10th 2009, 06:03 AM

Search Tags


/mathhelpforum @mathhelpforum