Can a set $A$ have exactly $2000$ subsets that are subsets of neither $B$, nor $C$? [closed]
Clash Royale CLAN TAG#URR8PPP
up vote
-1
down vote
favorite
Can a set $A$ have exactly $2000$ subsets that are subsets of neither $B$, nor $C$?
So I was trying to solve this problem, but I don't even know where to start. I have tried to find some patterns by making few examples, but the only one I've got is that the number of such type of subsets is always even, but that's pretty much it.
combinatorics
edited Aug 14 at 6:24
Asaf Karagila♦
293k31406735
asked Aug 14 at 3:45
Arci
646
closed as off-topic by ThomasGrubb, Servaes, Tyrone, Xander Henderson, Jendrik Stelzner Aug 17 at 2:08
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – ThomasGrubb, Servaes, Tyrone, Xander Henderson, Jendrik Stelzner
 |Â
show 1 more comment
up vote
-1
down vote
favorite
Can a set $A$ have exactly $2000$ subsets that are subsets of neither $B$, nor $C$?
So I was trying to solve this problem, but I don't even know where to start. I have tried to find some patterns by making few examples, but the only one I've got is that the number of such type of subsets is always even, but that's pretty much it.
combinatorics
edited Aug 14 at 6:24
Asaf Karagila♦
293k31406735
asked Aug 14 at 3:45
Arci
646
closed as off-topic by ThomasGrubb, Servaes, Tyrone, Xander Henderson, Jendrik Stelzner Aug 17 at 2:08
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – ThomasGrubb, Servaes, Tyrone, Xander Henderson, Jendrik Stelzner
You should provide more information about the question... What is $A, B,$ and $C$ ?? How do they look like ??
– Anik Bhowmick
Aug 14 at 4:05
The answer is not always even, e.g., $A=1,2,3$, $B=1,2$, $C=3$.
– David
Aug 14 at 4:13
1
@AnikBhowmick if there would be more information I would obviously provide it. But that's the whole problem.
– Arci
Aug 14 at 4:22
@David, Subsets that A has that B and C don't are 2,3; 1,3, which is an even number
– Arci
Aug 14 at 4:25
1
And $1,2,3$, making it odd.
– David
Aug 14 at 4:29
 |Â
show 1 more comment
up vote
-1
down vote
favorite
up vote
-1
down vote
favorite
Can a set $A$ have exactly $2000$ subsets that are subsets of neither $B$, nor $C$?
So I was trying to solve this problem, but I don't even know where to start. I have tried to find some patterns by making few examples, but the only one I've got is that the number of such type of subsets is always even, but that's pretty much it.
combinatorics
edited Aug 14 at 6:24
Asaf Karagila♦
293k31406735
asked Aug 14 at 3:45
Arci
646
Can a set $A$ have exactly $2000$ subsets that are subsets of neither $B$, nor $C$?
So I was trying to solve this problem, but I don't even know where to start. I have tried to find some patterns by making few examples, but the only one I've got is that the number of such type of subsets is always even, but that's pretty much it.
combinatorics
edited Aug 14 at 6:24
Asaf Karagila♦
293k31406735
asked Aug 14 at 3:45
Arci
646
edited Aug 14 at 6:24
Asaf Karagila♦
293k31406735
edited Aug 14 at 6:24
Asaf Karagila♦
293k31406735
edited Aug 14 at 6:24
Asaf Karagila♦
293k31406735
293k31406735
asked Aug 14 at 3:45
Arci
646
asked Aug 14 at 3:45
Arci
646
asked Aug 14 at 3:45
Arci
646
646
closed as off-topic by ThomasGrubb, Servaes, Tyrone, Xander Henderson, Jendrik Stelzner Aug 17 at 2:08
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – ThomasGrubb, Servaes, Tyrone, Xander Henderson, Jendrik Stelzner
closed as off-topic by ThomasGrubb, Servaes, Tyrone, Xander Henderson, Jendrik Stelzner Aug 17 at 2:08
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – ThomasGrubb, Servaes, Tyrone, Xander Henderson, Jendrik Stelzner
You should provide more information about the question... What is $A, B,$ and $C$ ?? How do they look like ??
– Anik Bhowmick
Aug 14 at 4:05
The answer is not always even, e.g., $A=1,2,3$, $B=1,2$, $C=3$.
– David
Aug 14 at 4:13
1
@AnikBhowmick if there would be more information I would obviously provide it. But that's the whole problem.
– Arci
Aug 14 at 4:22
@David, Subsets that A has that B and C don't are 2,3; 1,3, which is an even number
– Arci
Aug 14 at 4:25
1
And $1,2,3$, making it odd.
– David
Aug 14 at 4:29
 |Â
show 1 more comment
You should provide more information about the question... What is $A, B,$ and $C$ ?? How do they look like ??
– Anik Bhowmick
Aug 14 at 4:05
The answer is not always even, e.g., $A=1,2,3$, $B=1,2$, $C=3$.
– David
Aug 14 at 4:13
1
@AnikBhowmick if there would be more information I would obviously provide it. But that's the whole problem.
– Arci
Aug 14 at 4:22
@David, Subsets that A has that B and C don't are 2,3; 1,3, which is an even number
– Arci
Aug 14 at 4:25
1
And $1,2,3$, making it odd.
– David
Aug 14 at 4:29
You should provide more information about the question... What is $A, B,$ and $C$ ?? How do they look like ??
– Anik Bhowmick
Aug 14 at 4:05
You should provide more information about the question... What is $A, B,$ and $C$ ?? How do they look like ??
– Anik Bhowmick
Aug 14 at 4:05
The answer is not always even, e.g., $A=1,2,3$, $B=1,2$, $C=3$.
– David
Aug 14 at 4:13
The answer is not always even, e.g., $A=1,2,3$, $B=1,2$, $C=3$.
– David
Aug 14 at 4:13
1
1
@AnikBhowmick if there would be more information I would obviously provide it. But that's the whole problem.
– Arci
Aug 14 at 4:22
@AnikBhowmick if there would be more information I would obviously provide it. But that's the whole problem.
– Arci
Aug 14 at 4:22
@David, Subsets that A has that B and C don't are 2,3; 1,3, which is an even number
– Arci
Aug 14 at 4:25
@David, Subsets that A has that B and C don't are 2,3; 1,3, which is an even number
– Arci
Aug 14 at 4:25
1
1
And $1,2,3$, making it odd.
– David
Aug 14 at 4:29
And $1,2,3$, making it odd.
– David
Aug 14 at 4:29
 |Â
show 1 more comment
1 Answer
1
active
oldest
votes
up vote
3
down vote
accepted
Suppose that $B$ and $C$ are both subsets of $A$, that the number of elements in $A,B,C$ are $a,b,c$ respectively and that the number of elements in $Bcap C$ is $i$. Then the number of admissible subsets is
$$2^a-2^b-2^c+2^i ,$$
and we want to know if this can equal $2000$. The equation can be rewritten
$$2^a+2^i+2^5+2^4=2^b+2^c+2^11 .$$
Now if the LHS is a sum of four different powers of $2$, then it cannot be written as a sum of three powers of $2$. So two (at least) of $a,i,5,4$ must be equal, and it doesn't take much trial and error to find the solution
$$a=11,, b=5,, c=5,, i=4,.$$
So an example would be
$$A=1,2,3,4,5,6,7,8,9,10,11,,quad B=1,2,3,4,5,,quad C=2,3,4,5,6,.$$
Checking this, to get a subset of $A$ which is a subset neither of $B$ nor of $C$, we need
- a non-empty subset of $7,8,9,10,11$ together with any subset of $1,2,3,4,5,6$: there are $(2^5-1)2^6$ possibilities; or
- a subset of $1,2,3,4,5,6$ which includes both $1$ and $6$: there are $2^4$ possibilities.
Total, $31times64+16=2000$.
answered Aug 14 at 4:29
David
66.1k662125
Wow, thank you so much!
– Arci
Aug 14 at 4:31
How did you do the equation rewriting? where did 4, 5, 11 come from
– qwr
Aug 14 at 4:34
3
@qwr Hint: $2000$ is $2^11$ minus a bit. Give it a try.
– David
Aug 14 at 4:36
I am working through your answer and I understood everything except the main part, could you please explain how you derive the $2^a−2^b−2^c+2^i$ ?
– Arci
Aug 14 at 6:43
I hope I did not make any mistakes, but: if we take sets $ A = 1,2,3 , B = 6, 7, 8 $ and $C = 3, 5$ then number of the subsets of A that are not subset of B and C according to this formula is $2^3 - 2^3 - 2^2 + 2^0$ ?
– Arci
Aug 14 at 6:48
 |Â
show 3 more comments
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
Suppose that $B$ and $C$ are both subsets of $A$, that the number of elements in $A,B,C$ are $a,b,c$ respectively and that the number of elements in $Bcap C$ is $i$. Then the number of admissible subsets is
$$2^a-2^b-2^c+2^i ,$$
and we want to know if this can equal $2000$. The equation can be rewritten
$$2^a+2^i+2^5+2^4=2^b+2^c+2^11 .$$
Now if the LHS is a sum of four different powers of $2$, then it cannot be written as a sum of three powers of $2$. So two (at least) of $a,i,5,4$ must be equal, and it doesn't take much trial and error to find the solution
$$a=11,, b=5,, c=5,, i=4,.$$
So an example would be
$$A=1,2,3,4,5,6,7,8,9,10,11,,quad B=1,2,3,4,5,,quad C=2,3,4,5,6,.$$
Checking this, to get a subset of $A$ which is a subset neither of $B$ nor of $C$, we need
- a non-empty subset of $7,8,9,10,11$ together with any subset of $1,2,3,4,5,6$: there are $(2^5-1)2^6$ possibilities; or
- a subset of $1,2,3,4,5,6$ which includes both $1$ and $6$: there are $2^4$ possibilities.
Total, $31times64+16=2000$.
answered Aug 14 at 4:29
David
66.1k662125
Wow, thank you so much!
– Arci
Aug 14 at 4:31
How did you do the equation rewriting? where did 4, 5, 11 come from
– qwr
Aug 14 at 4:34
3
@qwr Hint: $2000$ is $2^11$ minus a bit. Give it a try.
– David
Aug 14 at 4:36
I am working through your answer and I understood everything except the main part, could you please explain how you derive the $2^a−2^b−2^c+2^i$ ?
– Arci
Aug 14 at 6:43
I hope I did not make any mistakes, but: if we take sets $ A = 1,2,3 , B = 6, 7, 8 $ and $C = 3, 5$ then number of the subsets of A that are not subset of B and C according to this formula is $2^3 - 2^3 - 2^2 + 2^0$ ?
– Arci
Aug 14 at 6:48
 |Â
show 3 more comments
up vote
3
down vote
accepted
Suppose that $B$ and $C$ are both subsets of $A$, that the number of elements in $A,B,C$ are $a,b,c$ respectively and that the number of elements in $Bcap C$ is $i$. Then the number of admissible subsets is
$$2^a-2^b-2^c+2^i ,$$
and we want to know if this can equal $2000$. The equation can be rewritten
$$2^a+2^i+2^5+2^4=2^b+2^c+2^11 .$$
Now if the LHS is a sum of four different powers of $2$, then it cannot be written as a sum of three powers of $2$. So two (at least) of $a,i,5,4$ must be equal, and it doesn't take much trial and error to find the solution
$$a=11,, b=5,, c=5,, i=4,.$$
So an example would be
$$A=1,2,3,4,5,6,7,8,9,10,11,,quad B=1,2,3,4,5,,quad C=2,3,4,5,6,.$$
Checking this, to get a subset of $A$ which is a subset neither of $B$ nor of $C$, we need
- a non-empty subset of $7,8,9,10,11$ together with any subset of $1,2,3,4,5,6$: there are $(2^5-1)2^6$ possibilities; or
- a subset of $1,2,3,4,5,6$ which includes both $1$ and $6$: there are $2^4$ possibilities.
Total, $31times64+16=2000$.
answered Aug 14 at 4:29
David
66.1k662125
Wow, thank you so much!
– Arci
Aug 14 at 4:31
How did you do the equation rewriting? where did 4, 5, 11 come from
– qwr
Aug 14 at 4:34
3
@qwr Hint: $2000$ is $2^11$ minus a bit. Give it a try.
– David
Aug 14 at 4:36
I am working through your answer and I understood everything except the main part, could you please explain how you derive the $2^a−2^b−2^c+2^i$ ?
– Arci
Aug 14 at 6:43
I hope I did not make any mistakes, but: if we take sets $ A = 1,2,3 , B = 6, 7, 8 $ and $C = 3, 5$ then number of the subsets of A that are not subset of B and C according to this formula is $2^3 - 2^3 - 2^2 + 2^0$ ?
– Arci
Aug 14 at 6:48
 |Â
show 3 more comments
up vote
3
down vote
accepted
up vote
3
down vote
accepted
Suppose that $B$ and $C$ are both subsets of $A$, that the number of elements in $A,B,C$ are $a,b,c$ respectively and that the number of elements in $Bcap C$ is $i$. Then the number of admissible subsets is
$$2^a-2^b-2^c+2^i ,$$
and we want to know if this can equal $2000$. The equation can be rewritten
$$2^a+2^i+2^5+2^4=2^b+2^c+2^11 .$$
Now if the LHS is a sum of four different powers of $2$, then it cannot be written as a sum of three powers of $2$. So two (at least) of $a,i,5,4$ must be equal, and it doesn't take much trial and error to find the solution
$$a=11,, b=5,, c=5,, i=4,.$$
So an example would be
$$A=1,2,3,4,5,6,7,8,9,10,11,,quad B=1,2,3,4,5,,quad C=2,3,4,5,6,.$$
Checking this, to get a subset of $A$ which is a subset neither of $B$ nor of $C$, we need
- a non-empty subset of $7,8,9,10,11$ together with any subset of $1,2,3,4,5,6$: there are $(2^5-1)2^6$ possibilities; or
- a subset of $1,2,3,4,5,6$ which includes both $1$ and $6$: there are $2^4$ possibilities.
Total, $31times64+16=2000$.
answered Aug 14 at 4:29
David
66.1k662125
Suppose that $B$ and $C$ are both subsets of $A$, that the number of elements in $A,B,C$ are $a,b,c$ respectively and that the number of elements in $Bcap C$ is $i$. Then the number of admissible subsets is
$$2^a-2^b-2^c+2^i ,$$
and we want to know if this can equal $2000$. The equation can be rewritten
$$2^a+2^i+2^5+2^4=2^b+2^c+2^11 .$$
Now if the LHS is a sum of four different powers of $2$, then it cannot be written as a sum of three powers of $2$. So two (at least) of $a,i,5,4$ must be equal, and it doesn't take much trial and error to find the solution
$$a=11,, b=5,, c=5,, i=4,.$$
So an example would be
$$A=1,2,3,4,5,6,7,8,9,10,11,,quad B=1,2,3,4,5,,quad C=2,3,4,5,6,.$$
Checking this, to get a subset of $A$ which is a subset neither of $B$ nor of $C$, we need
- a non-empty subset of $7,8,9,10,11$ together with any subset of $1,2,3,4,5,6$: there are $(2^5-1)2^6$ possibilities; or
- a subset of $1,2,3,4,5,6$ which includes both $1$ and $6$: there are $2^4$ possibilities.
Total, $31times64+16=2000$.
answered Aug 14 at 4:29
David
66.1k662125
edited Aug 15 at 0:10
answered Aug 14 at 4:29
David
66.1k662125
answered Aug 14 at 4:29
David
66.1k662125
answered Aug 14 at 4:29
David
66.1k662125
66.1k662125
Wow, thank you so much!
– Arci
Aug 14 at 4:31
How did you do the equation rewriting? where did 4, 5, 11 come from
– qwr
Aug 14 at 4:34
3
@qwr Hint: $2000$ is $2^11$ minus a bit. Give it a try.
– David
Aug 14 at 4:36
I am working through your answer and I understood everything except the main part, could you please explain how you derive the $2^a−2^b−2^c+2^i$ ?
– Arci
Aug 14 at 6:43
I hope I did not make any mistakes, but: if we take sets $ A = 1,2,3 , B = 6, 7, 8 $ and $C = 3, 5$ then number of the subsets of A that are not subset of B and C according to this formula is $2^3 - 2^3 - 2^2 + 2^0$ ?
– Arci
Aug 14 at 6:48
 |Â
show 3 more comments
Wow, thank you so much!
– Arci
Aug 14 at 4:31
How did you do the equation rewriting? where did 4, 5, 11 come from
– qwr
Aug 14 at 4:34
3
@qwr Hint: $2000$ is $2^11$ minus a bit. Give it a try.
– David
Aug 14 at 4:36
I am working through your answer and I understood everything except the main part, could you please explain how you derive the $2^a−2^b−2^c+2^i$ ?
– Arci
Aug 14 at 6:43
I hope I did not make any mistakes, but: if we take sets $ A = 1,2,3 , B = 6, 7, 8 $ and $C = 3, 5$ then number of the subsets of A that are not subset of B and C according to this formula is $2^3 - 2^3 - 2^2 + 2^0$ ?
– Arci
Aug 14 at 6:48
Wow, thank you so much!
– Arci
Aug 14 at 4:31
Wow, thank you so much!
– Arci
Aug 14 at 4:31
How did you do the equation rewriting? where did 4, 5, 11 come from
– qwr
Aug 14 at 4:34
How did you do the equation rewriting? where did 4, 5, 11 come from
– qwr
Aug 14 at 4:34
3
3
@qwr Hint: $2000$ is $2^11$ minus a bit. Give it a try.
– David
Aug 14 at 4:36
@qwr Hint: $2000$ is $2^11$ minus a bit. Give it a try.
– David
Aug 14 at 4:36
I am working through your answer and I understood everything except the main part, could you please explain how you derive the $2^a−2^b−2^c+2^i$ ?
– Arci
Aug 14 at 6:43
I am working through your answer and I understood everything except the main part, could you please explain how you derive the $2^a−2^b−2^c+2^i$ ?
– Arci
Aug 14 at 6:43
I hope I did not make any mistakes, but: if we take sets $ A = 1,2,3 , B = 6, 7, 8 $ and $C = 3, 5$ then number of the subsets of A that are not subset of B and C according to this formula is $2^3 - 2^3 - 2^2 + 2^0$ ?
– Arci
Aug 14 at 6:48
I hope I did not make any mistakes, but: if we take sets $ A = 1,2,3 , B = 6, 7, 8 $ and $C = 3, 5$ then number of the subsets of A that are not subset of B and C according to this formula is $2^3 - 2^3 - 2^2 + 2^0$ ?
– Arci
Aug 14 at 6:48
 |Â
show 3 more comments
You should provide more information about the question... What is $A, B,$ and $C$ ?? How do they look like ??
– Anik Bhowmick
Aug 14 at 4:05
The answer is not always even, e.g., $A=1,2,3$, $B=1,2$, $C=3$.
– David
Aug 14 at 4:13
1
@AnikBhowmick if there would be more information I would obviously provide it. But that's the whole problem.
– Arci
Aug 14 at 4:22
@David, Subsets that A has that B and C don't are 2,3; 1,3, which is an even number
– Arci
Aug 14 at 4:25
1
And $1,2,3$, making it odd.
– David
Aug 14 at 4:29