Can a set $A$ have exactly $2000$ subsets that are subsets of neither $B$, nor $C$?

Question

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.

Answer 1

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 $B\cap 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, $31\times64+16=2000$.