CMOQR 2014 Problem 2

Alphonse and Beryl play a game involving $n$ safes. Each safe can be opened by a unique key and each key opens a unique safe. Beryl randomly shuffles the $n$ keys, and after placing one key inside each safe, she locks all of the safes with her master key. Alphonse then selects $m$ of the safes (where $m < n$ ), and Beryl uses her master key to open just the safes that Alphonse selected. Alphonse collects all of the keys inside these $m$ safes and tries to use these keys to open up the other $n - m$ safes. If he can open a safe with one of the $m$ keys, he can then use the key in that safe to try to open any of the remaining safes, repeating the process until Alphonse successfully opens all of the safes, or cannot open any more. Let $P_m(n)$ be the probability that Alphonse can eventually open all $n$ safes starting from his initial selection of $m$ keys.

(a) Show that $P_2(3) = \frac23$ .

(b) Prove that $P_1(n) = \frac1n$ .

(c) For all integers $n \geq 2$ , prove that $$P_2(n) = \frac2n \cdot P_1(n-1) + \frac{n-2}{n} \cdot P_2(n-1).$$ (d) Determine a formula for $P_2 (n)$ .