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)$.
### Part (a)
1. We need to show that \( P_2(3) = \frac{2}{3} \).
2. Consider the three safes labeled \( A, B, \) and \( C \) and the three keys \( k_A, k_B, \) and \( k_C \) corresponding to these safes.
3. Beryl shuffles the keys and places one key in each safe randomly.
4. Alphonse selects 2 out of the 3 safes. Without loss of generality, assume he selects safes \( A \) and \( B \).
5. There are \( 3! = 6 \) possible permutations of the keys in the safes.
6. We need to count the number of permutations where Alphonse can eventually open all 3 safes.
7. If Alphonse can open all safes, the keys in safes \( A \) and \( B \) must allow him to open safe \( C \) directly or indirectly.
8. The favorable permutations are:
   - \( (k_A, k_B, k_C) \)
   - \( (k_A, k_C, k_B) \)
   - \( (k_B, k_A, k_C) \)
   - \( (k_B, k_C, k_A) \)
9. Out of the 6 permutations, 4 are favorable.
10. Therefore, \( P_2(3) = \frac{4}{6} = \frac{2}{3} \).

### Part (b)
1. We need to prove that \( P_1(n) = \frac{1}{n} \).
2. Alphonse selects 1 safe out of \( n \) safes.
3. The probability that the key inside the selected safe opens another safe is \( \frac{n-1}{n} \).
4. If the key opens another safe, the process continues with \( n-1 \) safes.
5. The probability that Alphonse can open all safes is the product of probabilities at each step.
6. The probability that the first key opens another safe is \( \frac{1}{n} \).
7. Therefore, \( P_1(n) = \frac{1}{n} \).

### Part (c)
1. We need to prove that 
   \[
   P_2(n) = \frac{2}{n} \cdot P_1(n-1) + \frac{n-2}{n} \cdot P_2(n-1).
   \]
2. Consider the first key Alphonse picks from the 2 selected safes.
3. There are two cases:
   - Case 1: The first key opens one of the remaining \( n-1 \) safes.
   - Case 2: The first key does not open any of the remaining \( n-1 \) safes.
4. In Case 1, the probability is \( \frac{2}{n} \) and Alphonse is left with \( n-1 \) safes and 1 key.
5. The probability of opening all safes in this case is \( P_1(n-1) \).
6. In Case 2, the probability is \( \frac{n-2}{n} \) and Alphonse is left with \( n-1 \) safes and 2 keys.
7. The probability of opening all safes in this case is \( P_2(n-1) \).
8. Therefore, 
   \[
   P_2(n) = \frac{2}{n} \cdot P_1(n-1) + \frac{n-2}{n} \cdot P_2(n-1).
   \]

### Part (d)
1. We need to determine a formula for \( P_2(n) \).
2. From part (b), we know \( P_1(n) = \frac{1}{n} \).
3. Using the recurrence relation from part (c):
   \[
   P_2(n) = \frac{2}{n} \cdot \frac{1}{n-1} + \frac{n-2}{n} \cdot P_2(n-1).
   \]
4. Simplify the first term:
   \[
   \frac{2}{n} \cdot \frac{1}{n-1} = \frac{2}{n(n-1)}.
   \]
5. Assume \( P_2(n-1) = \frac{2}{n-1} \).
6. Substitute into the recurrence relation:
   \[
   P_2(n) = \frac{2}{n(n-1)} + \frac{n-2}{n} \cdot \frac{2}{n-1}.
   \]
7. Simplify the second term:
   \[
   \frac{n-2}{n} \cdot \frac{2}{n-1} = \frac{2(n-2)}{n(n-1)}.
   \]
8. Combine the terms:
   \[
   P_2(n) = \frac{2}{n(n-1)} + \frac{2(n-2)}{n(n-1)} = \frac{2 + 2(n-2)}{n(n-1)} = \frac{2n-2}{n(n-1)} = \frac{2(n-1)}{n(n-1)} = \frac{2}{n}.
   \]
9. Therefore, the formula for \( P_2(n) \) is \( \frac{2}{n} \).

The final answer is \( \boxed{ \frac{2}{n} } \).