Question

$A = \{1,2,3,4,5,6,7\}$ $B = \{3,5,6,9\}$ $S = \{C: C \subset A \text{ and } C \cap B \neq \phi\}$

Answer 1

112

Answer 2

Let $A = \{1,2,3,4,5,6,7\}$ and $B = \{3,5,6,9\}$. We are looking for the number of subsets $C$ of $A$ such that $C \cap B \neq \phi$. The elements common to $A$ and $B$ are $A \cap B = \{3,5,6\}$. The condition $C \cap B \neq \phi$ means that the subset $C$ must contain at least one element from $\{3,5,6\}$.

The total number of subsets of $A$ is $2^{|A|} = 2^7 = 128$.

To find the number of subsets $C$ with $C \cap B \neq \phi$, we can subtract the number of subsets $C$ with $C \cap B = \phi$ from the total number of subsets of $A$. The condition $C \cap B = \phi$ means that $C$ contains no elements from $B$. Since $C$ must be a subset of $A$, this implies $C$ contains no elements from $A \cap B$. Thus, $C$ must be a subset of $A \setminus (A \cap B)$. $A \setminus (A \cap B) = \{1,2,3,4,5,6,7\} \setminus \{3,5,6\} = \{1,2,4,7\}$. The number of subsets of $\{1,2,4,7\}$ is $2^{|\{1,2,4,7\}|} = 2^4 = 16$. These are the subsets $C$ for which $C \cap B = \phi$.

The number of subsets $C$ of $A$ such that $C \cap B \neq \phi$ is: (Total number of subsets of $A$) - (Number of subsets $C$ of $A$ such that $C \cap B = \phi$) $= 2^7 - 2^4 = 128 - 16 = 112$.