CMI CS 2025 | Part A | Question: 6

Question

Let $X$ be a set of size $n.$ What is the size of the set $\{(A, B) \mid A, B \subseteq X, A \cap B=\varnothing\}$?

• A. $3^{n}-2^{n}$
• B. $3^{n}$
• C. $4^{n}$
• D. $2^{n+1}$

Answer 1

Each element of \(X\) only has three choices:
- It can go to set \(A\)
- It can go to set \(B\)
- It can go to neither  
(but not to both, since we have to satisfy \(A \cap B = \emptyset\))

So, the total number of pairs \((A, B)\) is:
\[
\boxed{\ 3^n}
\]

 

Answer 2

Answer: B