Key Concepts and Formulas

• Power Set: If a set $S$ has $n$ elements, it has $2^n$ subsets.
• Principle of Complementary Counting: The number of elements in a set satisfying a property $P$ is equal to the total number of elements minus the number of elements that do not satisfy property $P$. $|\text{Total}| = |\text{Satisfying P}| + |\text{Not satisfying P}|$ $|\text{Satisfying P}| = |\text{Total}| - |\text{Not satisfying P}|$
• Set Intersection: $A \cap B$ is the set of elements common to both $A$ and $B$.
• Set Difference: $A \setminus B$ is the set of elements in $A$ but not in $B$.

Step-by-Step Solution

We are given sets $A=\{1,2,3,4,5,6,7\}$ and $B=\{3,6,7,9\}$. We need to find the number of subsets $C$ of $A$ such that $C \cap B \neq \phi$.

Step 1: Understand the Problem and the Condition

The problem asks for the number of subsets $C$ of $A$ that have at least one element in common with set $B$. The condition $C \cap B \neq \phi$ means that the intersection of $C$ and $B$ is not empty, implying there is at least one element that belongs to both $C$ and $B$.

Step 2: Apply the Principle of Complementary Counting

Directly counting subsets $C$ that satisfy $C \cap B \neq \phi$ can be complicated as it involves considering subsets that share one element, two elements, etc., with $B$. It's more efficient to use the Principle of Complementary Counting.

The total number of possible subsets $C$ of $A$ is $2^{|A|}$. The complementary condition to $C \cap B \neq \phi$ is $C \cap B = \phi$. So, the number of subsets satisfying $C \cap B \neq \phi$ is: $(\text{Total number of subsets of } A) - (\text{Number of subsets } C \subseteq A \text{ such that } C \cap B = \phi)$

Step 3: Calculate the Total Number of Subsets of $A$

The set $A$ has 7 elements: $A=\{1,2,3,4,5,6,7\}$. The total number of subsets of $A$ is $2^{|A|} = 2^7$. $2^7 = 128$ So, there are 128 possible subsets of $A$.

Step 4: Determine the Condition for the Complementary Case ($C \cap B = \phi$)

The condition $C \cap B = \phi$ means that the subset $C$ must not contain any element that is present in set $B$. Since $C$ must be a subset of $A$, $C$ can only contain elements from $A$. Therefore, for $C \cap B = \phi$, $C$ must not contain any elements that are common to both $A$ and $B$.

Let's find the intersection of $A$ and $B$: $A \cap B = \{1,2,3,4,5,6,7\} \cap \{3,6,7,9\} = \{3,6,7\}$ So, for $C \cap B = \phi$, the subset $C$ cannot contain the elements $3, 6,$ or $7$.

Step 5: Calculate the Number of Subsets Satisfying the Complementary Condition

If $C$ cannot contain any of the elements $\{3,6,7\}$, then $C$ must be formed only from the elements of $A$ that are not in $B$. These are the elements in $A \setminus (A \cap B)$. $A \setminus (A \cap B) = \{1,2,3,4,5,6,7\} \setminus \{3,6,7\} = \{1,2,4,5\}$ Let $A' = \{1,2,4,5\}$. The number of elements in $A'$ is $|A'|=4$. Any subset $C$ of $A$ such that $C \cap B = \phi$ must be a subset of $A'$. The number of subsets of $A'$ is $2^{|A'|} = 2^4$. $2^4 = 16$ So, there are 16 subsets $C$ of $A$ such that $C \cap B = \phi$.

Step 6: Final Calculation using Complementary Counting

Now, we subtract the number of subsets satisfying the complementary condition from the total number of subsets of $A$. Number of subsets $C \subseteq A$ such that $C \cap B \neq \phi$ = (Total subsets of $A$) - (Subsets $C \subseteq A$ such that $C \cap B = \phi$) $= 2^7 - 2^4$ $= 128 - 16$ $= 112$

Common Mistakes & Tips

• Confusing Intersection with Membership: Remember that $C \cap B \neq \phi$ means "at least one common element," not that $C$ must contain all of $B$ or that $B$ must be a subset of $C$.
• Incorrectly Identifying Elements for Complementary Sets: When $C \cap B = \phi$, $C$ must not contain elements from $A \cap B$. Elements in $B$ but not in $A$ (like $9$) are irrelevant for forming subsets of $A$.
• Forgetting the Empty Set: The empty set is a subset of every set. In the complementary count ($C \cap B = \phi$), the empty set is indeed one of the $2^4$ subsets, as $\phi \cap B = \phi$.

Summary

This problem is effectively solved using the Principle of Complementary Counting. We first calculated the total number of subsets of $A$, which is $2^7 = 128$. Then, we identified the complementary condition: $C \cap B = \phi$. This means $C$ cannot contain any elements from $A \cap B = \{3,6,7\}$. Therefore, $C$ must be a subset of the remaining elements in $A$, which are $\{1,2,4,5\}$. The number of such subsets is $2^4 = 16$. Finally, we subtract the number of complementary subsets from the total number of subsets: $128 - 16 = 112$.

The final answer is $\boxed{112}$.