2024 SSMO Speed Round Problems/Problem 6

Problem

There are $4$ people and $4$ houses. Each person independently randomly chooses a house to live in. The expected number of inhabited houses can be expressed as $\frac{m}{n}$ , where $m$ and $n$ are relatively prime positive integers. Find $m+n$ .

Solution

Let $a_n$ equal $1$ if the nth house is occupied and $0$ if the nth house is unoccupied. Thus, we are trying to find $\mathbb{E}[a_1+a_2+a_3+a_4] = 4\mathbb{E}[a_1]$ by the Linearity of Expectation. Instead of calculating the probability that a single house is occupied, we instead calculate the probability that it is unoccupied. Each person has a $\frac{1}{4}$ chance of residing in that house, and thus a $\frac{3}{4}$ chance of not residing in that house. The probability that none of the people stay in that house is $\left (\frac{3}{4} \right)^4 = \frac{81}{256}$ . Thus, the probability that any given house is occupied, or $\mathbb{E}[a_1]$ , is $1 - \frac{81}{256} = \frac{175}{256}$ . Thus, our answer is $4\cdot \frac{175}{256} = \frac{175}{64}$ , $175+64=\boxed{239}$ .

-Vivdax

Page

Toolbox

Search

2024 SSMO Speed Round Problems/Problem 6

Problem

Solution