Safes and keys probability puzzle

Question

I have $100$ keys and $100$ safes. Each key opens only one safe, and each safe is opened only by one key. Every safe contains a random key. 98 of these safes are locked. What's the probability that I can open all the safes?

This question is confusing for me. Can you walk me through it step-by-step?

Answer 1

In order to open the safes, there must be at most two 'cycles' of safes and keys, and one unlocked safe in each cycle. Let $A \to B$ denote that safe A unlocks safe B. For example, if 1 and 98 are unlocked,

$$1 \to 2 \to 3 \to 4 \cdots \to 72 \to 1 \textrm{ and } 98 \to 99 \to 100 \to 73 \to 74 \to 75 \cdots \to 97 \to 98$$

is unlockable, but not if 1 and 2 are unlocked.

How many such pairs of cycles can you make? Keep in mind that there must be an unlocked safe in each cycle.

This should be $\frac{99}{2} \cdot 100!$ Say we have a cycle of size $n$. There are $\binom{100}{n}$ safes we can put in that cycle, and $n!$ ways we can arrange them. There are $(100 - n)!$ ways to arrange the other cycle. So there are $\binom{100}{n}n!(100-n)! = 100!$ arrangements where a cycle is size $n$. Thus, for all cycle sizes, we have $\sum_{i=1}^{99} 100! = 99 \cdot 100!$. But since we double-counted everything (every time we count a cycle of size $n$, we count one of size $100-n$ too), we must divide by 2: $\frac{99}{2} \cdot 100!$

The other possibility is that they form one large cycle, like $1 \to 2 \to 3 \to 4 \cdots \to 100 \to 1$. Count those up too. If there is a large cycle, then all combinations of unlocked safes allow everything to be unlocked.

This is (oddly enough) also $\frac{99}{2} \cdot 100!$. Say one of our unlocked safes is at the beginning of the sequence. There are $100!$ such sequences. Each of those has a possible 99 choices for the other unlocked safe. Again, we double count: a sequence starting with 1, where 2 is chosen, is equivalent to starting with 2, with 1 chosen. So we have $\frac{99}{2} \cdot 100!$ This means we have a total of $99 \cdot 100!$ arrangements that are unlockable.

Then, we compute how many arrangements are possible, unlockable or not.

$4950 \cdot 100!$. There are 100 keys we can put in the first box, 99 in the second, etc. Then we choose our unlocked safes: $\binom{100}{2} = 4950$ possible combinations. So the chance your arrangement is unlockable is $\frac{99 \cdot 100!}{4950 \cdot 100!} = \frac{1}{50}$, which is higher than I expected.

I think this generalizes nicely, actually:

It's always $\frac{2}{n}$. Weird.