Question

Let $A = \{1, 2, 3\}, B = \{4, 5, 6\}, C = \{7, 8, 9\}$ and $D = \{1, 2, 3, 4, 5, ... 10\}$, then total number of subsets of D having exactly one element from each of sets A, B and C is equal to

Answer 1

54

Answer 2

Let $A = \{1, 2, 3\}, B = \{4, 5, 6\}, C = \{7, 8, 9\}$, and $D = \{1, 2, 3, 4, 5, ..., 10\}$.

We are looking for the number of subsets $S$ of $D$ such that $S$ contains exactly one element from $A$, exactly one element from $B$, and exactly one element from $C$. This means $|S \cap A| = 1$, $|S \cap B| = 1$, and $|S \cap C| = 1$.

Let the element chosen from $A$ be $a \in A$. There are $|A| = 3$ choices for $a$. Let the element chosen from $B$ be $b \in B$. There are $|B| = 3$ choices for $b$. Let the element chosen from $C$ be $c \in C$. There are $|C| = 3$ choices for $c$.

Since $A$, $B$, and $C$ are disjoint sets, the elements $a$, $b$, and $c$ are distinct. Any subset $S$ satisfying the conditions must contain the set $\{a, b, c\}$ for some choice of $a \in A$, $b \in B$, and $c \in C$. So, $S$ must be of the form $\{a, b, c\} \cup S'$, where $S'$ is a subset of $D \setminus \{a, b, c\}$.

Now consider the conditions $|S \cap A| = 1$, $|S \cap B| = 1$, $|S \cap C| = 1$. We have $S \cap A = (\{a, b, c\} \cup S') \cap A = (\{a, b, c\} \cap A) \cup (S' \cap A)$. Since $a \in A$, $b \notin A$ (as $b \in B$ and $A \cap B = \emptyset$), and $c \notin A$ (as $c \in C$ and $A \cap C = \emptyset$), we have $\{a, b, c\} \cap A = \{a\}$. So, $S \cap A = \{a\} \cup (S' \cap A)$. For this to be equal to $\{a\}$, we must have $S' \cap A = \emptyset$. Similarly, for $|S \cap B| = 1$, we must have $S' \cap B = \emptyset$. And for $|S \cap C| = 1$, we must have $S' \cap C = \emptyset$.

Thus, $S'$ must be a subset of $D \setminus \{a, b, c\}$ such that $S'$ contains no elements from A, no elements from B, and no elements from C. This means $S'$ must be a subset of $D \setminus (A \cup B \cup C)$.

Let $E = D \setminus (A \cup B \cup C)$. $A \cup B \cup C = \{1, 2, 3\} \cup \{4, 5, 6\} \cup \{7, 8, 9\} = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$. $D = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$. $E = D \setminus (A \cup B \cup C) = \{10\}$. The set E contains the elements in D that are not in A, B, or C. The size of E is $|E| = 1$.

The subset S is formed by choosing one element $a \in A$, one element $b \in B$, one element $c \in C$, and including these three elements along with any subset of E. So, $S = \{a, b, c\} \cup S_E$, where $a \in A, b \in B, c \in C$ and $S_E \subseteq E$.

The number of ways to choose $a$ is $|A| = 3$. The number of ways to choose $b$ is $|B| = 3$. The number of ways to choose $c$ is $|C| = 3$. The number of ways to choose a subset $S_E$ from E is $2^{|E|} = 2^1 = 2$. The possible subsets of E={10} are $\emptyset$ and {10}.

The total number of such subsets S is the product of the number of choices for each part: Total number of subsets = (Number of choices for $a$) $\times$ (Number of choices for $b$) $\times$ (Number of choices for $c$) $\times$ (Number of choices for $S_E$) Total number of subsets = $|A| \times |B| \times |C| \times 2^{|D \setminus (A \cup B \cup C)|}$ Total number of subsets = $3 \times 3 \times 3 \times 2^1 = 27 \times 2 = 54$.

Each such choice gives a unique subset of D satisfying the conditions. For example, choosing $a=1, b=4, c=7$ and $S_E=\emptyset$ gives the subset $\{1, 4, 7\}$. Choosing $a=1, b=4, c=7$ and $S_E=\{10\}$ gives the subset $\{1, 4, 7, 10\}$. Choosing $a=2, b=5, c=8$ and $S_E=\emptyset$ gives the subset $\{2, 5, 8\}$. And so on.

The total number of subsets of D having exactly one element from each of sets A, B, and C is 54.