# Counting question on bit strings - problem with using cases

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.

## 2 Answers

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

• Ah. Well, I see that my problem involves not knowing that "either" also implied both in this context
– user502227
Commented Nov 25, 2018 at 0:34
• @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. Commented Nov 25, 2018 at 0:39

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