I've never been asked a question involving how many do not contain a specific string and I'm not quite sure how to go about answering this question.
How many 0,1 bit strings of length 10 are there which do not contain a string of 1001001?
-
0My answer had a minor problem, and since I posted it, there are many other answers now that should provide details on how to go about this process. – 2012-12-05
2 Answers
Hint, following on JavaMan's comment: You probably know there are $2^{10}$ total 10-bit strings. Now to contain $1001001$ you can have a string of the form $xxx1001001$ (where the $x$'s are either $1$ or $0$) or a few similar choices, so subtract them. The challenge comes in whether you have subtracted a string twice-so think about the various patterns and see if the same string can satisfy more than one.
-
0@Anthony: that is correct. – 2012-12-05
This problem is actually just a little tricky. JavaMan’s suggestion in the comments is the way to go, but there’s a little sting in the tail.
In a ten-bit string the seven-bit string $1001001$ can start at the first, second, third, or fourth bit. Each of those starting positions leaves $3$ bits that can be anything. Thus, there are $2^3=8$ ten-bit words of the form $1001001xxx$, $8$ more of the form $x1001001xx$, and so on, for a total of $4\cdot8=32$ ten-bit strings containing $1001001$.
BUT there might be some ten-bit strings that have $1001001$ starting in more than one of the four possible starting positions, and if so, we’ve counted those strings twice. A little thought reveals that there is exactly one such string, $1001001001$; we counted it once for $\color{red}{1001001}001$ and once for $100\color{red}{1001001}$. Thus, the number of strings containing the substring $1001001$ is really only $32-1=31$.
Finally, there are $2^{10}=1024$ ten-bit strings, so there are $1024-31=993$ that do not contain the substring $1001001$.
-
0@Anthony: You’re most welcome. – 2012-12-05