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.

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?

share|improve this question
add comment

1 Answer

up vote 4 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.

share|improve this answer
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
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.