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

AI Thread Summary
The discussion revolves around calculating the probability that no two zeros are adjacent in an 11-digit integer composed of the digits 1 and 0. The initial approach involved counting permutations and resulted in a probability of 3/64, but it was later corrected to 9/64. Participants explored the use of recurrence relations to define the number of valid sequences, leading to the conclusion that the relationship can be modeled similarly to the Fibonacci sequence. The final consensus is that the number of valid sequences can be expressed as f_n = f_{n-1} + f_{n-2}, where f_n represents the count of valid sequences of length n. The conversation highlights the complexity of combinatorial problems and the importance of recurrence relations in solving them.
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
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.
 
How do you find ##f_n##?
 
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.
 
  • #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?
 
  • #36
If r denotes the number of steps, fn=fn-1+fn-2
r=2, fn=fn-2+2fn-3+fn-4
For r=r, ##f_n=f_{n-r}+ \binom{r}{1}f_{n-r-1}+ \binom{r}{2}f_{n-r-2}+ ...##
 
  • #37
AdityaDev said:
If r denotes the number of steps, fn=fn-1+fn-2
r=2, fn=fn-2+2fn-3+fn-4
For r=r, ##f_n=f_{n-r}+ \binom{r}{1}f_{n-r-1}+ \binom{r}{2}f_{n-r-2}+ ...##
Well it would take me much time to understand that in correlation with your problem but I guess you have reached the answer?
 
  • #38
Raghav Gupta said:
Well it would take me much time to understand that in correlation with your problem but I guess you have reached the answer?
No. I am waiting @haruspex to check If its correct.
 
  • #39
AdityaDev said:
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}##
Bingo!
 
  • #40
haruspex said:
Bingo!
Whats the next step?
 
  • #41
I am excited on finally solving up your question.
It has been a lengthy thread.
Your attempt was on a right track but a few mistakes there.
I don't know why @haruspex brought you on a recurrence relation which is not taught in high school.
Maybe different thinking patterns.
AdityaDev said:

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:

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
First digit is obviously 1. Now considering all things from 2nd digit onwards.
When we have no zero in number then we have 10 ones and obviously that is one way.
When we have one zero in number then we have 9 ones.
Placing ones at alternate places.
_1_1_1_1_1_1_1_1_1_.
We have 10 spaces and one zero to place in any space, so number of ways = 10C1
When we have 2 zero in number then we have 8 ones
Placing ones at alternate places.
_1_1_1_1_1_1_1_1_
We have nine spaces and two zeroes to place in any space, so number of ways = 9C2= 36.
I hope you get the pattern and maximum zeroes we can have is 5.
Any further queries?
 
Last edited:
  • Like
Likes AdityaDev
  • #42
The answer 118/2^11 is not correct.
 
  • #43
AdityaDev said:
The answer 118/2^11 is not correct.
Where I have written that answer?
 
  • #44
AdityaDev said:
The answer 118/2^11 is not correct.
To whom you are referring?
 
  • #45
From post 41. I tried calculating.
 
  • #46
Haruspex dissapeared. He left me confused. I don't know how to proceed.
 
  • #47
But I am getting 144/210.
Which is 9/64.
Have you read my post 41 carefully.
What would be the ways of creating numbers having non adjacent zeroes when we have 3 zeroes.?
Are you following my pattern? It's easy.
 
  • #48
AdityaDev said:
The answer 118/2^11 is not correct.
I am getting both numerator and denominator different finally. I have given hints in 41. Do you understand?
Why 211 in denominator. It would be 210 as we have 10 spaces as obviously first digit is 1.
 
  • #49
Raghav Gupta said:
But I am getting 144/210.
Which is 9/64.
Have you read my post 41 carefully.
What would be the ways of creating numbers having non adjacent zeroes when we have 3 zeroes.?
Are you following my pattern? It's easy.
10C1+9C2+8C3+7C4+6C5
 
  • #50
AdityaDev said:
10C1+9C2+8C3+7C4+6C5
Yeah, I think you got it.
 

Similar threads

Probability of combination lock
Replies
2
Views
3K
Pascal - absolute sum of digits
Replies
4
Views
3K
From 000 to 999, probability exactly 1 digit is >5
Replies
6
Views
5K
Combinatorics: Choosing Sets of Distinct Digits
Replies
1
Views
3K
Probability theory and statistics
Replies
1
Views
1K
Calculating measurement probabilities for the CHSH game
Replies
2
Views
3K
Finding Correct Combination/Permutation Rule for Statistics Project
Replies
12
Views
4K
I Micromass' big October challenge
3
Replies
125
Views
19K
Is There a Positive Integer k Making k*2^n + 1 Composite for All n?
Replies
1
Views
2K
Mathematica This Week's Finds in Mathematical Physics (Week 228)
Replies
2
Views
3K

Hot Threads

Recent Insights

Back
Top