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

In summary: I am sorry. I am not able to understand the question.In summary, the probability of a positive integer with 11 digits formed by the digits 1, 0, or both having no two consecutive zeroes is 3/64. This is found by considering cases where there are 0, 1, 2, 3, 4, or 5 zeroes in the number and calculating the total number of possible combinations for each case.
  • #1
AdityaDev
527
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
  • #2
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:
  • #3
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)
 
  • #4
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.
 
  • #5
How do you find ##f_n##?
 
  • #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
 
  • #7
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?
 
  • #8
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.
 
  • #9
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.
 
  • #10
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?
 
  • #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.
 
  • #12
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?]
 
  • #13
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.
 
  • #14
##X_{r+1}=1+X_r## if x(r) is 0.
 
  • #15
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?
 
  • #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:
  • #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.
 
  • #18
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.
 
  • #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.
 
  • #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
 
  • #21
Post #20 gives the rule.
 
  • #22
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?
 
  • #23
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
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?
 
  • #25
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.
 
  • #26
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?
 
  • #27
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--------
 
  • #28
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?
 
  • #29
If you have x zeroes and n-1-x ones, the (n-1)!/x!(n-1-x)!
 
  • #30
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.
 
  • #31
haruspex said:
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
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
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------
 
  • #32
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}##
 
  • #33
AdityaDev said:
Got it...

So ##f_{n}=f_{n-1}+f_{n-2}##
It's like fibonacci seq.
How you'll find fn-1 and f n-2
 
  • #34
##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}##
 
  • #35
So in your question there are 10 spaces but if it would have been more then it would be a lengthy process?
 

Similar threads

  • Precalculus Mathematics Homework Help
Replies
2
Views
3K
  • Engineering and Comp Sci Homework Help
Replies
4
Views
3K
  • Calculus and Beyond Homework Help
Replies
6
Views
4K
  • Calculus and Beyond Homework Help
Replies
1
Views
3K
  • Calculus and Beyond Homework Help
Replies
1
Views
958
Replies
2
Views
2K
  • General Math
4
Replies
125
Views
17K
  • Set Theory, Logic, Probability, Statistics
Replies
12
Views
3K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
0
Views
1K
Back
Top