# Probability problem

Tags:
1. Feb 22, 2015

### AdityaDev

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

### AdityaDev

$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

### AdityaDev

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

### AdityaDev

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

### AdityaDev

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

### AdityaDev

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

### AdityaDev

$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

### AdityaDev

$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

### AdityaDev

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

### AdityaDev

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

### AdityaDev

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