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

Join the discussion
Registration is free. Start your own thread to ask a follow-up.
Sign up Log in
59 replies · 6K views
AdityaDev
Messages
527
Reaction score
33

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=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
 
Physics news on Phys.org

Discussion

AdityaDev said:
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}, ..##?
 
Last edited:
AdityaDev said:
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)
 
haruspex said:
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.
 
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
 
AdityaDev said:
##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?
 
Raghav Gupta said:
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.
 
haruspex said:
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.
 
AdityaDev said:
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?
 
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.
 
AdityaDev said:
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?]
 
No. I don't 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 don't get mad if I am not able to give the answer you want. I am a little slow.
 
AdityaDev said:
No. I don't 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 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?
 
##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:
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.
 
AdityaDev said:
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.
 
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.
 
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 said:
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?
 
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.
 
AdityaDev said:
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?
 
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.
 
AdityaDev said:
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?
 
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--------
 
AdityaDev said:
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?
 
If you have x zeroes and n-1-x ones, the (n-1)!/x!(n-1-x)!
 
AdityaDev said:
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.