1
$\begingroup$

How many bit-squences with length 8 has 1 as it's first bit and 00 as the two last bits(e.g $1011 1100$)

I thought the solution to this problem would be $1 * 2 * 2 * 2 * 2 * 2 * 1 * 1 = 2^5$, but my teacher proposed the following solution:

amount that starts with 1: $1 * 2 * 2 * 2 * 2 * 2 * 2 = 2^7$

amount that ends with 00: $2 * 2 * 2 * 2 * 2 * 2 * 1 * 1 = 2^6$

amount that starts with 1 and ends with 00: $1 * 2 * 2 * 2 * 2 * 2 * 1 * 1 = 2^5$

answer = $2^7 + 2^6 - 2^5 = 160$.


Isn't the amount of bit-squences that starts with 1 and ends with $00$ the answer to the question "How many bit-squences with length 8 has 1 as it's first bit and $00$ as the two last bits"? Isn't the answer simply $2^5$ ?

$\endgroup$
0
1
$\begingroup$

Yes, the answer is simply $2^5$. Your teacher is calculating some other count.

OK, your teacher is calculating the count of those sequences which start with 1 or end with 00. And she's using the inclusion exclusion principle for counting them.

Inclusion-Exclusion Principle

Maybe you misunderstood the problem. You thought there was an and there in the problem statement but it's actually an or.

$\endgroup$
1
  • $\begingroup$ ok thank you, the teacher made a mistake. She wrote and, but meant or. $\endgroup$ – Carefullcars Nov 6 '15 at 22:12

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.