0
$\begingroup$

Let $X$ be a set with $2021$ elements. Consider the set $$\mathcal{S} = \left\{(A,B,C): A,B,C\subseteq X,~ A\cap B = \emptyset, ~B\cap C = \emptyset,~ \text{ and }C\cap A = \emptyset\right\}.$$

Then what is the cardinality of the set $\mathcal{S}$?

I can only think of the following cases:

  • $\{(\emptyset,\emptyset,\emptyset)\}$
  • $\left|\{(\emptyset,\emptyset,C): \emptyset \neq C\subseteq X\}\right| = 2^{2021}-1$. Since we can permute these sets, the total number will be $\left(2^{2021}-1\right) \times 3$.

These cases become very tedious and look complicated. Any help/hint will be appreciated.

Thanks in advance!

$\endgroup$
3
  • 3
    $\begingroup$ Perhaps try counting the functions $f : \{1,...,2021\} \to \{0,...,3\}$? $\endgroup$
    – copper.hat
    Commented May 2, 2023 at 5:22
  • $\begingroup$ The total number of functions will be $4^{2021}$, but I am not getting how it will help. $\endgroup$
    – XYZABC
    Commented May 2, 2023 at 5:29
  • 1
    $\begingroup$ Think about which set, if any, the element $1$ is in. What about $2$? $\endgroup$
    – Calvin Lin
    Commented May 2, 2023 at 5:58

1 Answer 1

2
$\begingroup$

Let $X = \{1,2,\ldots,2021\}$. Let us count the ordered $3$-tuples $(A,B,C)$ such that intersection of any two is empty.

Following the hints provided in the comment, we note that for every $n\le 2021$, we have the following choices for $n$.

  • $n \in A,~ n\notin B,\text{ and } n \notin C$
  • $n \notin A,~ n\in B,\text{ and } n \notin C$
  • $n \notin A,~ n\notin B,\text{ and } n \in C$ and
  • $n \notin A,~ n\notin B,\text{ and } n \notin C$.

Therefore, the number of elements in the set $\mathcal{S}$ is $4^{2021}$.

$\endgroup$
1
  • 2
    $\begingroup$ Equivalently let $D=X \backslash (A \cup B\cup C)$ so each of the $2021$ elements of $X$ will be in exactly one of the $4$ of $A,B,C,D$ $\endgroup$
    – Henry
    Commented May 2, 2023 at 9:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .