\problemdata       % Takes 5 *mandatory* arguments
        {counting-24}             % latex-friendly label for the prob.
        {counting, inclusion-exclusion}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {F00 PS8-3;} % Usage (list ones you are aware of).
        {Jack Kwok, S02}        % Last revision info (author, date).

\begin{problem}{\bf Counting strings}

How many bit strings of length 10 contain either five consecutive $0$s
or five consecutive $1$s?

\solution{
There are $2^{10}$ bit strings of length 10. First, let's see how many of those contain five consecutive $0$'s. The sequence of the 5 $0$'s can start at position $1,2,3,4,5$ or $6$. In each case, the remaining $5$ bits are allowed to be anything, so, as a ``first approximation'', we can say that there are $6*2^5$ different strings of consecutive $0$'s. \par However, if we do this, we are \emph{overcounting} since, for example, the string that has its first $8$ bits equal to $0$ and the last $2$ equal to $1$ (that is, $0000000011$) will be counted as a valid string \emph{four times} by our method:  \underline{00000}00011, 0\underline{00000}0011, 00\underline{00000}011 and 000\underline{00000}11. We need to eliminate these duplicates, which occur whenever we are dealing with strings that have more than 5 consecutive $0$'s. \par

We can do this by calculating the number of strings with $6$ or more consecutive $0$'s using the same method as above. This will give us $5*2^4$ such strings, and for each sequence of $0$'s, we will be overcounting exactly one time less than we overcounted above: for example, going back to the string of $8$ consecutive $0$'s that was counted 4 times above, we see that this method will count it exactly $3$ times \underline{000000}0011, 0\underline{000000}011, 00\underline{000000}11.  The same will hold for all strings of length $\geq 6$ because the number of allowed starting positions for a sequence of $6$ $0$'s is exactly one less than the number of allowed starting positions for a sequence of $5$ consecutive $0$'s. Thus, it suffices to subtract this number from  the number we got before to get rid of duplicates. Therefore, the number of strings containing 5 or more consecutive $0$'s is
\[6*2^5-5*2^4=112\]
By symmetry, there are another 112 strings which contain five consecutive $1$'s. The question was to determine the number of strings that have either 5 $0$'s or 5 $1$'s. So, we are looking for the size of the union of those two sets (the bit strings with 5 $0$'s and the bit strings with 5 $1$'s). The intersection of the 2 sets (i.e, sequences that contain \emph{both} 5 $0$'s and 5 $1$'s) contains 2 elements: $0000011111$ and $1111100000$. Therefore, by the inclusion-exclusion principle, the size of the union of the two sets is $112+112-2=222$

}
\end{problem}
