1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Probability problem

  1. Feb 22, 2015 #1
    1. The problem statement, all variables and given/known data

    Consider a 11 digit positive integer formed by the digits 1,0 or both. The probability that no two zeros are adjacent is:
    2. Relevant equations

    None
    3. The attempt at a solution

    First digit has to be 1.

    Total number of permutations=210

    Now 1XXXXXXXXXX is the format.
    Taking 10 digits starting from 2nd digit, it has to be like 01X1X1X1X1 or it has to be like 1X1X1X1X1X.
    (X can be 0 or 1).

    For first case if I take one zero, it can be place in any of the 4 X = 4C1
    If I take 2 zero, 4C2 and so one because the other X has to be filled by 1.

    First case: 4c1+4c2+....+4c4=16
    Second case:5c1+...5c5=32

    Hence probability = (24+25)/210=3/64.
    But answer is 9/64
     
  2. jcsd
  3. Feb 22, 2015 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    There are other possibilities. E.g. ...11011011...

    Edit: hint, let ##f_n## be the number of such sequences of length n (allowing leading zero); can you find a relationship between ##f_n, f_{n-1}, f_{n-2}, ..##?
     
    Last edited: Feb 22, 2015
  4. Feb 22, 2015 #3

    phinds

    User Avatar
    Gold Member
    2016 Award

    Why do you believe this? (hint ... it's not true)

    (and I see haruspex beat me to it)
     
  5. Feb 22, 2015 #4
    ##f_1 = 2## 0 and 1
    ##f_2 = 2^2-1## each place has two options and the 00 case has to be subtracted.
    ##f_3 = 2^3-3## 001,100,000 removed
    ##f_3 = 2^4-7## 0001,0010,0100,1000,0000,1001,1100 has to be removed
    It keeps getting complicated.
     
  6. Feb 22, 2015 #5
    How do you find ##f_n##?
     
  7. Feb 22, 2015 #6
    I have another approach.
    Maximum number of zeroes in number would be 5 as they should not be adjacent.
    Now take 5 cases.
    When there are no zeroes in number you get one number where no adjacent zeroes.
    When there is 1 zero in number you get 10 numbers.
    When there are 5 zeroes you get 2 numbers.
    Now find for cases when there is 2,3,4 zeroes
     
  8. Feb 22, 2015 #7

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    No, I wasn't asking you to spot a pattern, though that could help. If you wish to pursue that, start with n=0, and your n=4 is wrong.
    I was suggesting to find a general relationship between ##f_n## and its predecessors. For an n digit sequence, the first is 0 or 1. If it is 0, how many ways of filling in the remaining n-1 positions? If the first digit is 0, how many ways?
     
  9. Feb 22, 2015 #8

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    There's an easier way.
     
  10. Feb 22, 2015 #9
    In an n digit sequence, If I fix first digit as zero, then I have to find the number of ways of filling the n-1places by 0 or 1 such that no zereos are adjacent.
    the second digit hast to be 1.
    the third digit has 2 choices.
    I am not able to find the relation.
     
  11. Feb 22, 2015 #10

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    OK so far. Having set the first two digits as 01, how does the number of possibilities for the remaining digits compare with ##f_{n-2}##?
    What about the case where the first digit is selected as 1?
     
  12. Feb 22, 2015 #11
    when first digit is 1, second digit is 1 or 0.
    second digit 0 -> 3rd digit 1 and second digit 1 -> 3rd digit 1 or zero.
     
  13. Feb 22, 2015 #12

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Yes, but that's not what I asked. Let's take the easier case first. If you fill in the first digit of the n as '1', how would you describe the rules for filling in the remaining digits? How does that compare with the rules for filling in the n digits (i.e. 'no two consecutive zeroes'?)
    [What I'm trying to get you to find is what is called a recurrence relation. Have you ever heard of these?]
     
  14. Feb 22, 2015 #13
    No. I dont what recurrence relation is.
    If rth digit is 1, then (r-1)th digit is 0 or 1 and (r+1)th digit is also 0 or 1.
    Please dont get mad if I am not able to give the answer you want. I am a little slow.
     
  15. Feb 22, 2015 #14
    ##X_{r+1}=1+X_r## if x(r) is 0.
     
  16. Feb 22, 2015 #15

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    OK, but please try to answer the question I ask, not some other question:
    The rule for filling in n digits is that no two consecutive digits are zero (I'm allowing a leading zero).
    If you fill in the first digit of the n as '1', how would you describe the rule for filling in the remaining digits?
     
  17. Feb 22, 2015 #16
    ##X_{r+1} = X_r+1## if ##X_r## is zero.
    ##X_{r+1} = X_r## or ##0## if ##X_r## is 1.
    ##X_r## is 0 or 1.
     
    Last edited: Feb 22, 2015
  18. Feb 22, 2015 #17
    Post #16# contains the rules. If the present digit x_r is 0, the 0+1 is the next digit.
    if it is 1, then 1 or zero.
     
  19. Feb 22, 2015 #18

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Still not quite what I asked. I asked for the rule for filling in the remaining digits. I'm not asking for anything complicated here - it's a very simple answer.
     
  20. Feb 22, 2015 #19
    The sum of any two adjacent digits has to to be one or two.
    difference of any two adjacent digits has to be -1,0,1
    Product of any two adjacent digits has to be 1 or zero.
    maximum sum of all digits is n.
    if you fill the sequence with x zeroes, the sum of all digits is n-x.
     
  21. Feb 22, 2015 #20
    Rule: if there are x zeroes, then the the digits must be filled with 1s such that sum of all digits is n-x
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Probability problem
  1. Probability problem (Replies: 4)

  2. Probability problem (Replies: 31)

  3. Probability problem (Replies: 6)

  4. Probability Problem (Replies: 6)

Loading...