1
$\begingroup$

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.

  • 0
    My 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 2

2

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
1

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