3
$\begingroup$

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!

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

1 Answer 1

2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

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