Key Concepts and Formulas

1. Cardinality of Cartesian Product: For two finite sets $A$ and $B$, the number of elements in their Cartesian product $A \times B$ is given by $n(A \times B) = n(A) \times n(B)$.
2. Total Number of Subsets: A set with $k$ elements has $2^k$ distinct subsets.
3. Number of Subsets of a Specific Size: For a set with $k$ elements, the number of subsets containing exactly $r$ elements is given by the binomial coefficient ${}^k C_r = \frac{k!}{r!(k-r)!}$.
4. Complementary Counting: To find the number of elements satisfying a condition, it is often easier to find the total number of elements and subtract those that do not satisfy the condition. This is particularly useful for "at least" problems.

---

Step-by-Step Solution

1. Determine the number of elements in the Cartesian product $A \times B$.

• Why this step: The problem asks about subsets of the set $A \times B$. To find the number of subsets, we first need to know the total number of elements in $A \times B$.
• Given:
  • Set A has four elements, so $n(A) = 4$.
  • Set B has two elements, so $n(B) = 2$.
• Calculation: Using the formula for the cardinality of a Cartesian product: $n(A \times B) = n(A) \times n(B) = 4 \times 2 = 8$ Thus, the set $A \times B$ contains 8 elements.

2. Calculate the total number of subsets of $A \times B$.

• Why this step: We are looking for a specific type of subset. To use the principle of complementary counting effectively, we first need to know the total number of possible subsets.
• Calculation: A set with 8 elements has $2^8$ subsets. $2^8 = 256$ Therefore, there are 256 possible subsets of $A \times B$.

3. Identify the condition and choose the most efficient counting strategy.

• Condition: We need to find the number of subsets of $A \times B$ that have "at least three elements". This means subsets with 3, 4, 5, 6, 7, or 8 elements.
• Strategy Selection: Calculating this directly would involve summing ${}^8 C_3 + {}^8 C_4 + {}^8 C_5 + {}^8 C_6 + {}^8 C_7 + {}^8 C_8$. This is cumbersome. The complementary counting principle is more efficient. The complement of "at least three elements" is "less than three elements," which means subsets with 0, 1, or 2 elements.

4. Calculate the number of subsets with "less than three elements" (the complement).

• Why this step: By calculating the number of subsets that do not meet our condition (i.e., subsets with 0, 1, or 2 elements), we can subtract this count from the total number of subsets to find our answer.
• Calculations:
  • Number of subsets with exactly 0 elements: This is the empty set, $\phi$. ${}^8 C_0 = \frac{8!}{0!(8-0)!} = 1$
  • Number of subsets with exactly 1 element: ${}^8 C_1 = \frac{8!}{1!(8-1)!} = \frac{8!}{1!7!} = 8$
  • Number of subsets with exactly 2 elements: ${}^8 C_2 = \frac{8!}{2!(8-2)!} = \frac{8!}{2!6!} = \frac{8 \times 7}{2 \times 1} = 28$
• Total number of subsets with less than three elements: $1 + 8 + 28 = 37$

5. Subtract the complementary count from the total number of subsets.

• Why this step: This is the final application of the complementary counting principle. We subtract the count of subsets that do not satisfy the condition from the total number of subsets to obtain the count of subsets that do satisfy the condition.
• Calculation: $\text{Number of subsets with at least three elements} = (\text{Total subsets}) - (\text{Subsets with less than three elements})$ $= 2^8 - ({}^8 C_0 + {}^8 C_1 + {}^8 C_2)$ $= 256 - 37$ $= 219$

---

Common Mistakes & Tips

• Confusing Union and Cartesian Product Cardinality: Remember that $n(A \times B) = n(A) \times n(B)$, not $n(A) + n(B)$.
• Forgetting the Empty Set: The empty set is always a subset and has 0 elements. Its count is ${}^n C_0 = 1$.
• Efficiency of Complementary Counting: For "at least" problems, always consider if calculating the complement ("at most" or fewer) simplifies the problem.

---

Summary

We are asked to find the number of subsets of $A \times B$ with at least three elements. First, we determined that $A \times B$ has $4 \times 2 = 8$ elements. The total number of subsets of $A \times B$ is $2^8 = 256$. Instead of summing the counts for subsets with 3, 4, 5, 6, 7, and 8 elements, we used complementary counting. We calculated the number of subsets with fewer than three elements: 0 elements (${}^8 C_0 = 1$), 1 element (${}^8 C_1 = 8$), and 2 elements (${}^8 C_2 = 28$). The total number of such subsets is $1 + 8 + 28 = 37$. Subtracting this from the total number of subsets gives us $256 - 37 = 219$.

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