A runner owns $k$ pairs of running shoes and runs twice a day. In the morning she leaves her house by the front door, and in the evening she leaves by the back door. On starting each run she looks for shoes by the door through which she exits, and runs barefoot if none are there. At the end of each run she is equally likely to return through the front or back doors. She removes her shoes (if any) and places them by the door. In the morning of day 1 all shoes are by the back door so she must run barefoot.

Let $p_{00}^{(n)}$ be the probability that she runs barefoot on the morning of day $n+1$. What conditions are satisfied in this problem which ensure $\lim _{n \rightarrow \infty} p_{00}^{(n)}$ exists? Show that its value is $1 / 2 k$.

Find the expected number of days that will pass until the first morning that she finds all $k$ pairs of shoes at her front door.