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?

up vote 5 down vote accepted

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
    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. – ccorn Nov 17 '13 at 16:15

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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