bit string question

Question

The question originally asked for four consecutive $1$s; this is the question that two of the answers address. It was later changed to ask for five consecutive $1$s.

How many bit strings of length $10$ contain either five consecutive $0$'s or five consecutive $1$'s?

Can someone please help with figuring out an approach? I'm not sure I have the correct answer. I got $296$.

Do you literally mean "either or", or do you want to include the case where both occur? — joriki, Mar 07 '13 at 19:36
There were two correct answers, one with three upvotes, when you changed the question without marking the change. Please don't do that; the additional effort of adding a short note explaining that you'd misstated the question is negligible compared to the confusion you cause if you don't. — joriki, Mar 08 '13 at 16:42

score 3 · Answer 1 · answered Mar 07 '13 at 19:56

6 types for five $0$'s:

XXXX100000
XXX100000X
XX100000XX
X100000XXX
100000XXXX
00000XXXXX

$5 \cdot 2^4 + 2^5 = 112$

7 types for four $1$'s:

XXXXX01111  !!! 1 repeat with (1) and 2 with (2)
XXXX01111X  !!! 2 repeats with (2)
XXX01111XX
XX01111XXX
X01111XXXX
01111XXXXX  !!! (1)
1111XXXXXX  !!! (2)

$6 \cdot 2^5 + 2^6 - 5 = 251$

They intersect in 8 obvious cases, so the answer is $112 + 251 - 8 = 355$

score 1 · Answer 2 · answered Mar 07 '13 at 20:06

A string of at least five $0$s contains one more string of exactly five $0$s than it contains strings of exactly six $0$s. Thus we can count each such string exactly once by subtracting the number of strings of exactly six $0$s from the number of strings of exactly five $0$s, which yields $6\cdot2^5-5\cdot2^4$.

Applying the same approach to strings of at least four $1$s yields $7\cdot2^6-6\cdot2^5$, for a total of $7\cdot26-5\cdot2^4=368$. However, this double-counts strings that either contain two separate strings of at least four $1$s, or both a string of at least four $1$s and a string of at least five $0$s. There are $5$ of the former and $8$ of the latter, so the answer is $368-13=355$.

The set of admissible strings supports a fixed point free involution, namely the interchanging of $0$ and $1$. Therefore its cardinality should be even. — Christian Blatter, Mar 08 '13 at 16:35
@Christian: A good example why it's such a bad idea to change the question without marking the change when there are already correct answers... — joriki, Mar 08 '13 at 16:39

score 1 · Answer 3 · answered Mar 08 '13 at 16:35

Computing $$y_i:=x_{i+1}-x_i \quad {\rm mod}\ 2\qquad(1\leq i\leq9)$$ transforms any admissible string into a string of length $9$ containing a run of $4$ zeroes. Conversely: To any such string of length $9$ correspond exactly two admissible strings.

A string of length $9$ containing a run of $4$ zeroes begins with $0000$ or contains a unique substring of the form $10000$. There are $2^5$ strings of the first kind and $5\cdot 2^4$ strings of the second kind. The string $000010000$ belongs to both classes. It follows that there are $32+5\cdot 16-1=111$ strings of length $9$ containing a run of $4$ zeroes.

Therefore the number of admissible strings of length $10$ is $222$.

Applying the first part of my answer twice and subtracting $2$ for the two double-counted strings yields the same answer $222$ to the modified question. — joriki, Mar 08 '13 at 16:47

bit string question

3 Answers3