This weeks Riddler Express is a problem about a frustrating elevator! Here it goes:
You are on the 10th floor of a tower and want to exit on the first floor. You get into the elevator and hit 1. However, this elevator is malfunctioning in a specific way. When you hit 1, it correctly registers the request to descend, but it randomly selects some floor below your current floor (including the first floor). The car then stops at that floor. If it’s not the first floor, you again hit 1 and the process repeats.
Assuming you are the only passenger on the elevator, how many floors on average will it stop at (including your final stop, the first floor) until you exit?
My solution:
[Show Solution]
Let $a_n$ be the expected number of button presses required to reach floor $1$ when starting at floor $n$. Clearly, we have $a_1=0$, and for the other $a_n$, it will take us one button press, plus however many more we accrue at our destination. Since each floor below us is equally likely, this means we have the recursion:
\[
a_{n+1} = 1+\frac{1}{n}\left( a_1+a_2+\cdots+a_n \right)\qquad\text{for }n=1,2,\dots
\]Multiply this by $n$, and write out the equation for two consecutive $n$ values:
\begin{align}
n a_{n+1} &= n + a_1 + a_2 + \cdots + a_n \\
(n-1) a_n &= (n-1) + a_1+ a_2+\cdots + a_{n-1}
\end{align}Now subtract the second equation from the first, and obtain:
\[
n a_{n+1}-(n-1)a_n = 1 + a_n
\]Rearranging and simplifying, we obtain
\[
a_{n+1}=a_n+\frac{1}{n}
\]This nice recursion, together with $a_1=0$, gives us a formula for the expected number of button presses from any floor:
$\displaystyle
a_n = 1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n-1}\qquad\text{for }n=2,3,4,\dots
$
If we start at the 2nd floor, it should take us exactly one button press to reach the first floor, since this is the only place the elevator can take us. The formula confirms that $a_2=1$. If we start at the 3rd floor, the formula says $a_3=1+\frac{1}{2}=\frac{3}{2}$. This also makes sense. Half of the time it will take us 1 press, the other half of the time it takes us 2 presses, and $\frac{3}{2}$ is the average of 1 and 2.
Continuing in this fashion, we can answer the original problem, which is the case $n=10$.
\[
a_{10} = 1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{9} = \frac{7129}{2520} \approx 2.82897
\]
Alternative solution
An alternative solution, courtesy of Ross Boczar, is to derive the recursion more directly using conditional expectation.
\begin{align}
a_{n+1} &= \mathbb{E}( \text{stops if we start at }n+1) \\[2mm]
&= \mathbb{E}(\text{stops}\;|\;\text{didn’t stop at }n)\cdot\mathbb{P}(\text{didn’t stop at }n) \\
&\hspace{2cm} + \mathbb{E}(\text{stops}\;|\;\text{stopped at }n)\cdot\mathbb{P}(\text{stopped at }n) \\[2mm]
&= a_n \left( 1-\frac{1}{n}\right) + \left(1+a_n\right)\frac{1}{n} \\
&= a_n + \frac{1}{n}
\end{align}