In a string like "00110101010000111001111011111000" I'm reliably informed that the number of intervals containing consecutive zeros and consecutive ones can only differ by 1. It kind of makes sense, but I'm having trouble seeing why it is true.

Can anyone please provide a proof?

This is what I've got so far:

Suppose we start with 0. Then either the string ends before a 1 is reached and the conditions holds, or a new interval begins consisting of ones. Either this new interval consisting of ones is the final interval, so the condition holds, or there is a new interval consisting of zeros...

Is this just ridiculously simple or do I need to use some tool like proof by induction?


You are correct. An easier way to see this is by concatenating groups of $0$s as $A$ and concatenating groups of $1$ as $B$.

Now, all binary strings can be simplified and written like this


Can you see why the condition holds?

| cite | improve this answer | |
  • 1
    $\begingroup$ That certainly helps. It gave me this: Starts with A, ends with A: |A| = |B| + 1 Starts with A, ends with B: |A| = |B| Starts with B, ends with A: |A| = |B| Starts with B, ends with B: |A| = |B| - 1 Is that a proof though? I think almost but not quite. What else does it need? $\endgroup$ – Robin Andrews Apr 9 at 17:13
  • $\begingroup$ That proof is correct $\endgroup$ – h-squared Apr 9 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.