2
$\begingroup$

How many bit strings of length 10 either begin with three 0s or end with two 0s?

I solved this question using cases but I do not seem to be getting the answer of $352$.

My attempt: Consider two cases:

  • Case 1: The string begins with three $0$s and does not end with two $0$s. There is only $1$ way to choose the first three bits, $2^5$ ways for the middle bits, and $3$ ways for the last two bits ($4$ ways to construct a string of two bits, minus $1$ way to make three $0$s). There are $2^5 \cdot 3$ ways to construct strings of this type.
  • Case 2: The string does not begin with three $0$s but ends with two $0$s. There are $2^3 - 1 = 7$ ways to choose the first three bits without three $0$s, $2^5$ ways for the middle bits, and $1$ way for the last two bits. There are $7 \cdot 2^5$ ways to construct strings of this type.

By the rule of sum, there are $2^5 \cdot 3 + 2^5 \cdot 7 = 320$ ways to construct bit strings of length 10 either begin with three $0$s or end with two $0$s.

$\endgroup$
3
$\begingroup$

You are missing the strings that both begin with three zeroes and end with two zeroes.

And since there are five bits left that can be anything, you have $2^5=32$ of those, exactly the difference

$\endgroup$
2
  • $\begingroup$ Ah. Well, I see that my problem involves not knowing that "either" also implied both in this context $\endgroup$ – user502227 Nov 25 '18 at 0:34
  • 1
    $\begingroup$ @holo Yeah, sometimes we use ‘either .. or’ to indicate an exclusive disjunction, but that is not always the case. For example, if I say that I would like to be either rich or happy, obviously I would not mind being rich and happy. $\endgroup$ – Bram28 Nov 25 '18 at 0:39
2
$\begingroup$

$$\underbrace{2^7}_{\text{begin with three zeros}}+\underbrace{2^8}_{\text{end with two zeros}}-\underbrace{2^5}_{\text{double-count}} $$

$\endgroup$

Your Answer

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