Counting question on bit strings - problem with using cases
up vote
2
down vote
favorite
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.
combinatorics discrete-mathematics
add a comment |
up vote
2
down vote
favorite
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.
combinatorics discrete-mathematics
add a comment |
up vote
2
down vote
favorite
up vote
2
down vote
favorite
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.
combinatorics discrete-mathematics
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.
combinatorics discrete-mathematics
combinatorics discrete-mathematics
asked 3 hours ago
holo
1538
1538
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
up vote
3
down vote
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
– holo
3 hours ago
@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.
– Bram28
3 hours ago
add a comment |
up vote
1
down vote
$$underbrace{2^7}_{text{begin with three zeros}}+underbrace{2^8}_{text{end with two zeros}}-underbrace{2^5}_{text{double-count}} $$
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
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
– holo
3 hours ago
@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.
– Bram28
3 hours ago
add a comment |
up vote
3
down vote
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
– holo
3 hours ago
@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.
– Bram28
3 hours ago
add a comment |
up vote
3
down vote
up vote
3
down vote
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
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
answered 3 hours ago
Bram28
58.3k44185
58.3k44185
Ah. Well, I see that my problem involves not knowing that "either" also implied both in this context
– holo
3 hours ago
@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.
– Bram28
3 hours ago
add a comment |
Ah. Well, I see that my problem involves not knowing that "either" also implied both in this context
– holo
3 hours ago
@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.
– Bram28
3 hours ago
Ah. Well, I see that my problem involves not knowing that "either" also implied both in this context
– holo
3 hours ago
Ah. Well, I see that my problem involves not knowing that "either" also implied both in this context
– holo
3 hours ago
@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.
– Bram28
3 hours ago
@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.
– Bram28
3 hours ago
add a comment |
up vote
1
down vote
$$underbrace{2^7}_{text{begin with three zeros}}+underbrace{2^8}_{text{end with two zeros}}-underbrace{2^5}_{text{double-count}} $$
add a comment |
up vote
1
down vote
$$underbrace{2^7}_{text{begin with three zeros}}+underbrace{2^8}_{text{end with two zeros}}-underbrace{2^5}_{text{double-count}} $$
add a comment |
up vote
1
down vote
up vote
1
down vote
$$underbrace{2^7}_{text{begin with three zeros}}+underbrace{2^8}_{text{end with two zeros}}-underbrace{2^5}_{text{double-count}} $$
$$underbrace{2^7}_{text{begin with three zeros}}+underbrace{2^8}_{text{end with two zeros}}-underbrace{2^5}_{text{double-count}} $$
answered 3 hours ago
David Peterson
8,55621935
8,55621935
add a comment |
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3012277%2fcounting-question-on-bit-strings-problem-with-using-cases%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown