Probability of Non-Adjacent Zeros in 11-Digit Integer with 1 and 0 Digits

[AdityaDev]

Homework Statement

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

Homework Equations

None

The Attempt at a Solution

First digit has to be 1.

Total number of permutations=2¹⁰

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 = (2⁴+2⁵)/2¹⁰=3/64.
But answer is 9/64

 

[haruspex]

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

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}, ..$?

 

[phinds]

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

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

(and I see haruspex beat me to it)

 

[AdityaDev]

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}, ..$?

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

 

[AdityaDev]

How do you find $f_n$?

 

[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

 

[haruspex]

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

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?

 

[haruspex]

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

There's an easier way.

 

[AdityaDev]

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?

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.

 

[haruspex]

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 has to be 1.
the third digit has 2 choices.

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?

 

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

 

[haruspex]

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.

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

 

[AdityaDev]

No. I don't what recurrence relation is.
If r^th digit is 1, then (r-1)th digit is 0 or 1 and (r+1)th digit is also 0 or 1.
Please don't get mad if I am not able to give the answer you want. I am a little slow.

 

[AdityaDev]

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

 

[haruspex]

No. I don't what recurrence relation is.
If r^th digit is 1, then (r-1)th digit is 0 or 1 and (r+1)th digit is also 0 or 1.
Please don't get mad if I am not able to give the answer you want. I am a little slow.

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?

 

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

 

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

 

[haruspex]

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.

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.

 

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

 

[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

 

[AdityaDev]

Post #20 gives the rule.

 

[haruspex]

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.he remaining digits? Is it any differe
maximum sum of all digits is n.
if you fill the sequence with x zeroes, the sum of all digits is n-x.

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?

 

[AdityaDev]

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.

 

[haruspex]

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.

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

 

[AdityaDev]

Rule for filling the remaining digits if the the number starts with digit 1.
01-------
And 1------- are the sequences.
the rule for filling -------- is same.

 

[haruspex]

Rule for filling the remaining digits if the the number starts with digit 1.
01-------
And 1------- are the sequences.
the rule for filling -------- is same.

Yes!

So we define $f_n$ as the number of such sequences of n digits, for any n.
If we fill in the first digit of n digits as 1 then there are n-1 digits remaining. The rule for filling those in is the same as before, but now there are only n-1 digits. So, using our $f$ sequence, how many ways are there of filling in those remaining digits?

 

[AdityaDev]

The rule for filling n-1digits:
the n-1 th digit can be zero or one. If it is zero, the n-2 th digit is 1 and the rule is same as that of filling digits in 01------ which will give 101-------
If the n-1 th digit is 1, then the rule is same as that of filling 1------ which will give me the sequence 11--------

 

[haruspex]

The rule for filling n-1digits:
the n-1 th digit can be zero or one. If it is zero, the n-2 th digit is 1 and the rule is same as that of filling digits in 01------ which will give 101-------
If the n-1 th digit is 1, then the rule is same as that of filling 1------ which will give me the sequence 11--------

I'm trying to get you to express the answer to my question using the $f_n$ sequence.
By definition, the number of ways of filling in n-1 digits with no two adjacent zeroes is $f_{n-1}$. Pretend that you knew this number. Suppose it's 999. Now you have n digits to fill in. You fill in the first as a 1, say. How many ways of filling in the rest?

 

[AdityaDev]

If you have x zeroes and n-1-x ones, the (n-1)!/x!(n-1-x)!

 

[haruspex]

If you have x zeroes and n-1-x ones, the (n-1)!/x!(n-1-x)!

No, most of those would not obey the rule.
Please try to understand the hints I'm giving you. If I make it any clearer I'll simply be giving you the answer! Your answer to my question should involve the f sequence I defined.

 

[Raghav Gupta]

I'm trying to get you to express the answer to my question using the $f_n$ sequence.
By definition, the number of ways of filling in n-1 digits with no two adjacent zeroes is $f_{n-1}$. Pretend that you knew this number. Suppose it's 999. Now you have n digits to fill in. You fill in the first as a 1, say. How many ways of filling in the rest?

But that's difficult finding the ways of filling in the rest.
Though there may be another way but we can generalize pattern

$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
It keeps getting complicated.

$f_4= 2^4-8$
$f_n = 2^n-some pattern$
That pattern is finding nth term for sequence
0, 1, 3, 8, 16, 27------

 

[AdityaDev]

Got it...
$f_n$ starting with zero is equal to $f_{n-2}$
$f_n$ starting with one is equal to $f_{n-1}$
So $f_{n}=f_{n-1}+f_{n-2}$

 

[Raghav Gupta]

Got it...

So $f_{n}=f_{n-1}+f_{n-2}$

It's like fibonacci seq.
How you'll find f_n-1 and f _n-2

 

[AdityaDev]

$f_n=f_{n-1}+f_{n-2}$
$f_{n-1}=f_{n-2}+f_{n-3}=f_{n-3}+2f_{n-4}+f_{n-5}=...$ coefficients are part of pascals triangle.
$f_{n-2}=f_{n-3}+f_{n-4}$

 

[Raghav Gupta]

So in your question there are 10 spaces but if it would have been more then it would be a lengthy process?