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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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

6 types for five $0$'s:


$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)
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|cite|improve this answer

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|cite|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

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|cite|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

Your Answer


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.