This problem looks simple, but for some reason I am stuck with it.

There is a circle of bits (0s and 1s) with the following constraints:

  • There is no run of 4 or more consecutive identical bits.
  • The number of $0$'s is $4$ plus the number of $1$'s.

Now we count the number of pairs of consecutive 0's and 1's. The pairs don't have to be disjoint (i.e. "000" counts as two pairs). My question is: can we prove that the number of $00$'s is larger then the number of $11$'s?


1 Answer 1


Let's say there are in total $n_0$ zeros and $n_1$ ones, with $n_0=n_1+4$.

Given such a configuration, consider the number $k$ of clockwise transitions from $0$ to $1$ on the circle. Between two adjacent transitions, the number of 00 pairs will be exactly one less than the number of 0s, likewise the number of 11 pairs will be exactly one less than the number of 1s, and no pair can occur across the transition.

Therefore the total numbers $n_{00}$ resp. $n_{11}$ of 00 resp. 11 pairs are $$\begin{align}n_{00} &= n_0-k\\n_{11} &= n_1-k\end{align}$$ and therefore $$n_{00}-n_{11} = n_0 - n_1 = 4$$ which proves your proposition.

  • 1
    $\begingroup$ Note that this does not even require the run-length limitation. That limitation would result in a lower bound on $k$, but $k$ drops out of the argument, so that does not matter. $\endgroup$
    – ccorn
    Nov 17, 2013 at 16:15

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.