4. Kyle secretly selects a subset of $\{1,2,3,4\}$. Albert also secretly selects a subset of $\{1,2,3,4\}$. What is the probability that their chosen subsets have at least one element in common?
Answer: $\frac{175}{256}$
Solution: Let $A$ and $B$ be the subsets selected by Kyle and Albert, respectively. We first find the probability that two subsets $A$ and $B$ are disjoint. For each $k \in\{0,1, \ldots, 4\}$, we choose an arbitrary subset $A$ with $k$ elements. In order for $A$ and $B$ to be disjoint, $B$ must be a subset of the complement $\{1,2,3,4\} \backslash A$ with $4-k$ elements. Thus, for each $k \in\{0,1, \ldots, 4\}$, there are $\binom{4}{k}$ subsets with $k$ elements and fixing one of such subsets (say $A$ ), there are $2^{4-k}$ choices for $B$ (note that $2^{4-k}$ is the number of subsets of $\{1,2,3,4\} \backslash A)$. We see that the number of ordered pairs $(A, B)$ of subsets with $A \cap B=\varnothing$ is
$$
\sum_{k=0}^{4}\binom{4}{k} 2^{4-k}=16 \sum_{k=0}^{4}\binom{4}{k}\left(\frac{1}{2}\right)^{k}=16\left(1+\frac{1}{2}\right)^{4}=81 .
$$

As there are $2^{4}=16$ subsets of $\{1,2,3,4\}$, there are $16^{2}=256$ possible ordered pairs of subsets. Hence, the probability that two subsets $A$ and $B$ are disjoint is $\frac{81}{256}$ and the probability that $A$ and $B$ have at least one element in common is $1-\frac{81}{256}=\frac{175}{256}$.