HMMT February, 2019

Combinatorics Difficulty 6.2 National Olympiad Prove it United States

Problem:
On floor $0$ of a weird-looking building, you enter an elevator that only has one button. You press the button twice and end up on floor $1$ . Thereafter, every time you press the button, you go up by one floor with probability $\frac{X}{Y}$ , where $X$ is your current floor, and $Y$ is the total number of times you have pressed the button thus far (not including the current one); otherwise, the elevator does nothing.

Between the third and the $100^{\text{th}}$ press inclusive, what is the expected number of pairs of consecutive presses that both take you up a floor?

Proposed by: Kevin Yang

Solution

Solution:
By induction, we can determine that after $n$ total button presses, your current floor is uniformly distributed from $1$ to $n-1$ : the base case $n=2$ is trivial to check, and for the $n+1$ th press, the probability that you are now on floor $i$ is $\frac{1}{n-1}\left(1-\frac{i}{n}\right)+\frac{1}{n-1}\left(\frac{i-1}{n}\right)=\frac{1}{n}$ for $i=1,2,\ldots,n$ , finishing the inductive step.

Hence, the probability that the $(n+1)$ -th and $(n+2)$ -th press both take you up a floor is
$\frac{1}{n-1} \sum_{i=1}^{n-1} \frac{i}{n} \cdot \frac{i+1}{n+1} = \frac{\sum_{i=1}^{n-1} i^2 + i}{(n-1)n(n+1)} = \frac{\frac{(n-1)n(2n-1)}{6} + \frac{n(n-1)}{2}}{(n-1)n(n+1)} = \frac{1}{3}$
Since there are $100-3=97$ possible pairs of consecutive presses, the expected value is $\frac{97}{3}$ .

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.