HMMT-Feb 2018 guts, Problem 27

There are 2018 frogs in a pool and there is 1 frog on the shore. In each time-step thereafter, one random frog moves position. If it was in the pool, it jumps to the shore, and vice versa. Find the expected number of time-steps before all frogs are in the pool for the first time.

Solution: Consider the general case of $n$ frogs. Let $E_{i}$ be the expected time for all frogs to enter the pool when $i$ frogs are on the shore and $n-i$ frogs are in the pool. We have $E_{0}=0, E_{n}=1+E_{n-1}$, and \[ E_{i}=\frac{i}{n} E_{i-1}+\frac{n-i}{n} E_{i+1}+1 \] for $0<i<n$. Define $f_{i}$ so that \[ E_{i}=\frac{f_{i}}{(n-1)(n-2) \cdots(i)}+E_{i-1} \] Then by plugging this equation into the first equation, we can show that \[ f_{i}=n(n-1) \cdots(i+1)+(n-i) f_{i+1} \] Furthermore, we know that $f_{n}=1$. Therefore \[ \begin{aligned} f_{1} & =\sum_{i=1}^{n} \frac{n !}{i !} \frac{(n-1) !}{(n-i) !} \\ & =(n-1) ! \sum_{i=1}^{n}\left(\begin{array}{c} n \\ i \end{array}\right) \\ & =(n-1) !\left(2^{n}-1\right) \end{aligned} \] Therefore \[ E_{1}=\frac{(n-1) !\left(2^{n}-1\right)}{(n-1) !}+E_{0}=2^{n}-1 \] Plugging in $n=2018$ yields $E_{1}=2^{2018}-1$. $\fbox{2^{2018}-1}$.

Answer: 2^{2018}-1