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.

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$.

share|improve this question
    
Do you literally mean "either or", or do you want to include the case where both occur? –  joriki Mar 7 '13 at 19:36
    
include the case where both exist –  Sara Meyer Mar 7 '13 at 19:42
    
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 8 '13 at 16:42
add comment

3 Answers

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$

share|improve this answer
add comment

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$.

share|improve this answer
    
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 8 '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 8 '13 at 16:39
add comment

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$.

share|improve this answer
    
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 8 '13 at 16:47
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.