# 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!

• This was a very nice first post, and welcome to math.se! Commented Jul 23, 2022 at 4:47
• Welcome to MathSE. This tutorial explains how to typeset mathematics on this site. Commented Jul 23, 2022 at 9:55
• The proof for $n$ candles is no harder and has a nice closed form. $\frac{2^{2n}-3^n}{2^{2n}}$
– sku
Commented Jul 26, 2022 at 4:43

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}.$$