Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider strings of 10 digits; there are $10^{10}$ possible such strings.

Among these strings, there are strings that contain sequence(s) of $n$ consecutive zeroes, for $n\le 10$. For example, $$4000000123$$ is one of the strings that contain a sequence of 6 consecutive zeroes.

I am attempting to find how many strings of 10 digits contains $n$ consecutive zeroes.

My early solution is $(m+1)10^m$ where $m=10-n$, which comes from the following consideration.

First, there is only one string that contains 10 consecutive zeroes, i.e.

$$0000000000$$

Next, there are $2\times 10$ strings that contains 9 consecutive zeroes, that is

$$000000000x, x000000000$$

where $x$ can be any digit. And next, there are $3\times 10^2$ string that contains 8 consecutive zeroes:

$$00000000xy,x00000000y,xy00000000$$

and so on. Therefore, there are $(m+1)10^m$, $m=10-n$, that contains $n$ consecutive zeroes.

But I am not convinced that this solution is correct. Because for $n=0$, i.e. strings that contain any number, I get $11\times 10^{10}$, which is greater than $10^{10}$, the number all possible strings!

What is the reason of this failure and what is the correct solution?

share|improve this question
1  
Your solution fails for all $n < 10$ because you're double-counting. For instance, for $n = 9$ you're counting $0000000000$ twice: once where $x = 0$ on the left, and once where $x = 0$ on the right. –  Amit Kumar Gupta Jul 10 '13 at 8:41
1  
Just for clarification -- a string containing a block of 7 consecutive zeroes should also count as having 6, 5, 4, ... 0 consecutive zeroes too, right? E.g. for $n=0$, you'd get the answer to be $10^{10}$ and for $n=1$ it'd be $10^{10}-9^{10}$ (all strings, apart from those having no zeroes at all); is that correct? –  Peter Košinár Jul 10 '13 at 8:52
add comment

1 Answer

In my experience, if it is difficult to calculate a probability, it is sometimes easier to calculate the inverse.

So how many 10 digit strings do not contain consecutive 0s?

We can ignore the first digit since one digit in of itself will have no impact on the probability.

From there, the probability that a single digit does not cause that string to contain consecutive 0s is inverse of the the probability that both the previous and the current digits are 0.

So if we were solving for 2 digit strings, the probability would simply be the inverse of the probability of having 0 digit followed by another 0 digit, or $1 - (\frac{1}{10\times10})$.

If we were to then apply this to a 3 digit string, the probability would be compounded with the inverse of the probability of the last digits having 0. This simply means to find the probability of not finding 0s in the first two digits and not finding 0s in the second two digits. This also covers the case of both finding digits in the first 2 digits as well as finding digits in the last 2 digits.

The probability of the first two digits not both having 0 is $1 - (\frac{1}{10\times10})$, and the probability of the last two digits not both having 0 is $1 - (\frac{1}{10\times10})$. Compounded, you would get $$1 - \frac{1}{\frac{1}{1 - (\frac{1}{10\times10})}\times\frac{1}{1 - (\frac{1}{10\times10})}}$$ Simplying a bit, we get: $$1 - (1 -\frac{1}{10\times10})^{2}$$

Why the 2? Because we have 3 digits and 2 pairs of digits to consider. Generalizing, we would have: $$1 - (1 - \frac{1}{10\times10})^{n-1}$$ Where $n$ is the number of digits. Take this probability and multiply times $10^n$ or in this case $10^{10}$ (total number of possible combinations) and you get the number of digits containing consecutive zeros.

It would seem that you're making the mistake of assuming the pattern is linear. When you're finding all configurations of non-0 digits in the case in which m is 1, there should be just as many configurations of 0 digits in the case in which m is 9. So: $$xxxxxxxxx0,0xxxxxxxxx$$

If your linear calculation were accurate, then there should be 10000000000 ways to place that singular 0 digit! Hope that helps!

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.