MAT (Math Advance Tournament) Problem - More Efficient Solutions? - Combinatorics I am a student going into high school next year. Recently, I came across a question from the MAT (Math Advance Tournament) that I spent too long on, but had solved in the end. With the lack of an explained solution on their solutions page, I want to ask the internet for criticism on my solution and possible more efficient solutions for this problem. 
The problem is as follows:
Steven has $4$ lit candles and each candle is blown out with a probability $1/2$. After he finishes blowing, he randomly selects a possibly empty subset out of all the candles. The probability his subset has at least one lit candle equals $\frac{m}{n}$ for relatively prime positive integers $m$ and $n$. Find $m + n$.
My Solution:
I first started by writing out all of the possible combinations of blown out and "un-blown out" candles: 
a = not blown out 
b = blown out 
aaaa aaab bbaa bbba bbbb 
     aaba baba bbab 
     abaa abba babb 
     baaa abab abbb
          aabb

A total of $16$ combinations.
I then manually calculated the number of combinations that includes at least one lit candle for every possible size of a subset Steven could have chosen giving me the following:
subset size:  0   1   2   3   4
combinations: 0  32  72  56  15

Then calculating the sum of the combinations: $32 + 72 + 56 + 15 = 175$
And the total: $16 + 4 \cdot 16 + (4 \cdot 3) \cdot 16 + \left(\frac{4 \cdot 3}{2}\right) \cdot 16 + \left(\frac{4 \cdot 3 \cdot 2}{3!}\right) \cdot 16 + 16 = 16 + 64 + 96 + 64 + 16 = 256$
Putting it into a fraction, I get $\frac{175}{256}$. It also happens that $175$ and $256$ are relatively prime, so my answer would be $175+256=431$, which turns out to be the correct answer.

Sorry for the messy work, this is my first problem posted on Stack Exchange.
Thank you in advance!
 A: Here's one way to think about this. Since each candle remains lit with probability $1/2$, the set of lit candles is actually a uniformly random subset of the set of $4$ candles. So the problem boils down to:

Let $X_1$ and $X_2$ be uniformly random subsets of $\{1,2,3,4\}$. Find the probability that $X_1 \cap X_2$ is not empty.

Instead, let's find the probability that $X_1 \cap X_2$ is empty, then subtract from $1$. This is mostly straightforward; we have:
$$P(X_1 \cap X_2 = \varnothing) = \frac{1}{16} \sum_{X \subseteq \{1,2,3,4\}} P(X \cap X_2 = \varnothing).$$
Now for a fixed $X \subseteq \{1,2,3,4\}$, the number of subsets of $\{1,2,3,4\}$ disjoint from $X$ is $2^{4-\lvert X \rvert}$, so $P(X \cap X_2 = \varnothing) = 2^{4 - \lvert X \rvert}/2^4 = 2^{-\lvert X \rvert}$. Thus we have
$$P(X_1 \cap X_2 = \varnothing) = \frac{1}{16} \sum_{X \subseteq \{1,2,3,4\}} 2^{-\lvert X \rvert} = \frac{1}{16} \sum_{i=0}^4 \binom{4}{i} 2^{-i}.$$
By the binomial theorem, this becomes
$$P(X_1 \cap X_2 = \varnothing) = \frac{1}{16} \sum_{i=0}^4 \binom{4}{i} 2^{-i} = \frac{1}{16} (1 + 2^{-1})^4 = \frac{1}{16} \cdot \frac{81}{16} = \frac{81}{256}.$$
So the probability that $X_1 \cap X_2$ is not empty is $\frac{175}{256}$. $175$ and $256$ are relatively prime, so the answer is $175+256 = 431$.

Or, even more simply:
$$P(X_1 \cap X_2 = \varnothing) = \prod_{x \in \{1,2,3,4\}} P(x \notin X_1 \cap X_2) = \prod_{x \in \{1,2,3,4\}} (1 - P(x \in X_1) P(x \in X_2)) = \prod_{x \in \{1,2,3,4\}} \frac{3}{4} = \frac{81}{256}.$$
