# Homework Help: Probability problem

Tags:
1. Feb 22, 2015

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. Feb 22, 2015

### haruspex

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
3. Feb 22, 2015

### phinds

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

(and I see haruspex beat me to it)

4. Feb 22, 2015

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

5. Feb 22, 2015

How do you find $f_n$?

6. Feb 22, 2015

### Raghav Gupta

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

7. Feb 22, 2015

### haruspex

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?

8. Feb 22, 2015

### haruspex

There's an easier way.

9. Feb 22, 2015

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.

10. Feb 22, 2015

### haruspex

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?

11. Feb 22, 2015

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.

12. Feb 22, 2015

### haruspex

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?]

13. Feb 22, 2015

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.

14. Feb 22, 2015

$X_{r+1}=1+X_r$ if x(r) is 0.

15. Feb 22, 2015

### haruspex

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?

16. Feb 22, 2015

$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
17. Feb 22, 2015

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.

18. Feb 22, 2015

### haruspex

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.

19. Feb 22, 2015

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.

20. Feb 22, 2015

Rule: if there are x zeroes, then the the digits must be filled with 1s such that sum of all digits is n-x

21. Feb 22, 2015

Post #20 gives the rule.

22. Feb 22, 2015

### haruspex

You're overthinking my question.

For the full n digits, the rule is "no two consecutive zeroes".

If the first digit is a 1, what is the rule for the remaining digits? Is it any different from the rule for all n?

What if the first digit is a zero? You already noted that the second digit must be 1. So, having set the first two digits as '01', what is the rule for the remaining n-2 digits? Is it any different from the rule for all n?

23. Feb 22, 2015

Ok. If the the first digit is zero, the second digit is 1. Then the rule for fillng the n-2 digits is same as the the rule for filling n digits starting from 1.

24. Feb 22, 2015

### haruspex

What do you mean by 'starting from 1' here?

25. Feb 22, 2015