HMMT-Nov 2009 team, Problem 8

Mario is once again on a quest to save Princess Peach. Mario enters Peach's castle and finds himself in a room with 4 doors. This room is the first in a sequence of 2 indistinugishable rooms. In each room, 1 door leads to the next room in the sequence (or, for the second room, into Bowser's level), while the other 3 doors lead to the first room. Suppose that in every room, Mario randomly picks a door to walk through. What is the expected number of doors (not including Mario's initial entrance to the first room) through which Mario will pass before he reaches Bowser's level?

Solution: Let $E_{i}$ be the expected number of doors through which Mario will pass in the future if he is currently in room $i$ for $i=1,2,3$ (we will set $E_{3}=0$ ). We claim that $E_{i}=1+\frac{3}{4} E_{1}+\frac{1}{4} E_{i+1}$. Indeed, the 1 at the beginning comes from the fact that we need to pass through a door to leave the room, the ${ }_{4}^{3} E_{1}$ comes from the fact that there is a $\frac{3}{4}$ chance of ending up in room 1 , and the $\frac{1}{4} E_{i+1}$ corresponds to the fact that there is a $\frac{1}{4}$ chance of ending up in $E_{i+1}$. Using this, we get $E_{1}=1+\frac{3}{4} E_{1}+\frac{1}{4} E_{2}$, or $E_{1}=4+E_{2}$. We also get $E_{2}=1+\frac{3}{4} E_{1}$. Solving this system of equations yields $E_{1}=20$. $\fbox{20}$.

Answer: 20