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

The question : How many bit strings of length 10 either begin with three $0$s or end with two $0$'s?

My solution : $0$ $0$ $0$ X X X X X $0$ $0$ = $2^5 = 256$

editing** I noticed the word"or" so I changed the solution to

$2^7$ (three $0$'s) +$2^8$(two $0$'s) - $2^5$(both) =416

is this the correct way to do it?

• This is begin with three and end with two. But it will be useful later. Note that $2^5=32$. Edit: With the change, it is OK, except that when it came to calculating you added instead of subtracting. – André Nicolas Nov 7 '15 at 1:19
• I need to subtract. Thank you! – guest11 Nov 7 '15 at 1:35
• You are welcome. You had the idea right. – André Nicolas Nov 7 '15 at 1:48
• when I see the word "or" I just need to follow these rule? and when I see the word " and" I just use my first solution,right? – guest11 Nov 7 '15 at 1:50
• Possible duplicate of Permutations of bit-sequence(discrete math) – Matt Samuel Nov 7 '15 at 2:54

## 2 Answers

These are the binary words $000x$ ($2^7$ many $x$) and $y00$ ($2^8$ many $y$) minus $000z00$ ($2^5$ many $z$). Looks good.

But I calculate $352$.

• I added them ,my mistake. – guest11 Nov 7 '15 at 1:36

Unfortunately not. :/ When you say the possible strings are 2^5 you're stand fixed the three 0 at beginning and the two 0 at end. You need to count each case separately:

First case - Three 0 at beginning: The first, second and third numbers just can take 0 value, so 1^3. Now you have the five middle numbers, which match to 2^5. The two numbers at final... if you count as 2^2, you are counting the "0001001100" for example. When you count the second case you need to pay attention to don't count this case again. To leave this problem away, we count the cases where the two final numbers are not 0 at same time. So we have 2x1. For the first case we have 1^3 + 2^5 + 2x1 = 1+32+2 = 35 (wrong) ---editing----

## For the first case we have 1^3 x 2^5 x 2x1 = 1x32x2 = 64

The second case - 00 at final: Here we have the middle numbers at normal way 2^5, and the final two are just 2^1. As the first case, now we have a similar problem: we can't count 000... again. So let's count the first three number with at least one be 1... 1x2^2. Total: 2^5+2^1+1x2^2 = 32+2+4 = 38 (wrong) ---editing----

## Total: 2^5 x 2^1 x 1x2^2 = 32 x 2 x 4 = 256

Now, all cases: 64+256+32, this +32 at final is because of the cases weren't counted, the cases 000xxxxx00, so total 352

Sorry for the english, I've never explained math in english before.

------- editing -----------

My mistake at beginning was sum the possibilities, where the foundamental principal of counting says we need to times them. We need to sum just the separated cases.

• The English is fine but it appears the math is wrong. – Matt Samuel Nov 7 '15 at 2:59
• Yeah, I just discoved what is wrong... I summed the possibilities instead times them. I changed but let my mistake visible because more people will take this same mistake. – Enrique René Nov 7 '15 at 18:18