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.
  • #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}+ ...##
 
Physics news on Phys.org
  • #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.
 
  • #51
So can we say you have understood and got the answer?
 
  • #52
Raghav Gupta said:
That pattern is finding nth term for sequence
0, 1, 3, 8, 16, 27------
The last two terms are wrong, should be 19 and 43.
AdityaDev said:
Haruspex dissapeared. He left me confused. I don't know how to proceed.
hey, I have to sleep sometime. (7:30am here now.)
Having got the recurrence relation, it is a trivial matter to work through from the smaller numbers:
f0=1, f1=2, so f2=1+2=3, etc. up to f10=144.
As to whether this method is too 'advanced', I would not have thought so. You don't need to know it is called a recurrence relation, and you don't need to solve the relation (i.e. find a general formula for fn). It's more like applying induction. You need to spot that having filled in the first digit the problem for the remaining digits hasn't changed much.

The 10C1+8C3+... method is fine too. It involves rather more calculation though. If you spot the recurrence method, it's much easier.
 
  • Like
Likes AdityaDev
  • #53
haruspex said:
hey, I have to sleep sometime. (7:30am here now.).
we are in different timezones then. My 2:22 am is your 7:30 am!
 
  • #54
AdityaDev said:
10C1+9C2+8C3+7C4+6C5
There should be 11C0 term = 1 also considering no zeroes in number. :smile:
haruspex said:
Having got the recurrence relation, it is a trivial matter to work through from the smaller numbers:
f0=1, f1=2, so f2=1+2=3, etc. up to f10=144.
As to whether this method is too 'advanced', I would not have thought so. You don't need to know it is called a recurrence relation, and you don't need to solve the relation (i.e. find a general formula for fn). It's more like applying induction. You need to spot that having filled in the first digit the problem for the remaining digits hasn't changed much.
But how you got f10 fast? It would take time to add that numbers starting from f0 unless you use a software.
It's like fibonacci series where there are no first two terms 0, 1.
I think you may have applied Binet's formula? But it is also lengthy, considering the powers and not using calculator.
Haruspex left me. He made me confused that how to proceed.
How you know that Haruspex is he/she.:biggrin:
According to wikipedia-Haruspex
 
Last edited:
  • #55
Raghav Gupta said:
How you know that Haruspex is he/she.:biggrin:
According to wikipedia-Haruspex
That does not matter. I got my doubt cleared and I am happy. Even if haruspex is a she.. what difference does it make?
 
  • #56
I was just joking.
But how we get f10 fast? Do we have to add all terms starting from f0
I got my doubt cleared and I am happy
I think you meant question and not doubt.
 
Last edited:
  • #57
Raghav Gupta said:
But how you got f10 fast? It would take time to add that numbers starting from f0 unless you use a software.
It's like fibonacci series where there are no first two terms 0, 1.
f(0) = 1, f(1) = 2 easy
after that
1+2=3
2+3=5
3+5=8
5+8=13
8+13=21
13+21=34
21+34=55
34+55=89
55+89=144
Done. Isn't that simpler than working out all those combinatorial functions? But I suppose you used an app/spreadsheet for that.
It might not be obvious to you that f(0)=1, so start with f(1) and f(2) by hand instead.

One benefit of my approach is that it scales. You can easily deduce the asymptotic behaviour.
Putting the two approaches together yields an interesting result about the sum of a combinatorial series.
 
  • #58
Thanks, I learned other approach but what if there were more spaces instead of 10. Now should we use Binet's formula? In software we can make loops for calculating that nth term for a recurrence relation and here it's easy because there were only 10 spaces.
In my approach there is a sequence for finding nth term.
 
Last edited:
  • #59
Raghav Gupta said:
Thanks, I learned other approach but what if there were more spaces instead of 10. Now should we use Binet's formula? In software we can make loops for calculating that nth term for a recurrence relation and here it's easy because there were only 10 spaces.
In my approach there is a sequence for finding nth term.
Even if there's no effort obtaining the combinatorial terms in your series, you still have to add n of them (or n/2, maybe). Using Fibonacci, you have to add n terms, but no combinatorials to calculate.
Ultimately, Binet may be fastest. You'd have to round to nearest integer, but I'm sure you could go a long way before that might go wrong.
 
  • Like
Likes Raghav Gupta
  • #60
Yeah that's true, I agree with you. Ultimately it comes to the person in the first place how to originate approach from his mind.
I never have seen that approach by anyone in my school and it's a kinda gem for me.
 
  • Like
Likes AdityaDev

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
956
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