3
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

marked as duplicate by ShreevatsaR, rschwieb, Micah, Jim, Amzoti Apr 15 '13 at 17:56

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nice answer but this part seems wrong: "There are $\binom{100}{n}$ safes we can put in that cycle, and $n!$ ways we can arrange them." When you have $n$ safes not every arrangement is guaranteed to be just one loop... $\endgroup$ – timidpueo Apr 14 '13 at 13:44
  • $\begingroup$ I wasn't super clear about it, but I meant "there are $\binom{100}{n}$ cycles of this size. And note that I'm really picking where the keys go, so that a cycle forms; the safes themselves don't move. $\endgroup$ – Henry Swanson Apr 14 '13 at 14:45
  • $\begingroup$ Wow, thanks for explaining this so that a high school student could understand it. Someone I was talking to in real life said something about Markov Chains, which is way beyond me. $\endgroup$ – user72273 Apr 15 '13 at 10:07
  • 1
    $\begingroup$ With respect to your last comment: I showed in another answer here that for general $k$ and $n$, the answer is always $k/n$. $\endgroup$ – ShreevatsaR Apr 15 '13 at 17:30
  • $\begingroup$ @ShreevatsaR While I'd like to study your answer, it's too advanced for me I think. The answer by Mr. Swanson makes sense to me, and so is useful to me. Maybe this question should be revised to "explainable at a high school level". $\endgroup$ – user72273 Apr 15 '13 at 19:11

Not the answer you're looking for? Browse other questions tagged or ask your own question.