One Hundred Lockboxes of Wood and Steel

Question

A bit beyond perceptions reach,
I sometimes believe I see
that life is two locked boxes, each
containing the other’s key.
― Piet Hein

You have one hundred lockboxes, fifty made of steel, fifty made of wood. You only have one copy of each box's key.

A prankster breaks into your house and randomly places the 100 keys in the boxes, one key per box. He then shuts all the boxes, locking the keys inside.

Though the steel boxes are impenetrable, the wooden ones can be broken quite easily. What is the probability that breaking open the wooden boxes will allow you to open all of the steel ones?

Answer 1

The probability is $1/2$.

We have a permutation that maps each box to the box whose key it contains. Once we open a box, we can open the box it maps to. So, we can open all the boxes exactly if there is no all-steel cycle.

Label the boxes $1$ through $100$. We denote the permutation in cycle format like $(31)(542)(6)$. To make this canonical, write each cycle with the greatest number first, and sort the cycles by increasing first number. Now, we can extract the cycle structure just from the sequence $315426$ because the cycles start at numbers that greater any before them ($3$, $5$, $6$). So, each of the $n!$ such sequences represents one of the $n!$ permutations.

Now, let the steel boxes be $1$ through $50$ and wooden boxes be $51$ through $100$. There's a steel cycle exactly if the first number is at most $50$. If so, the first cycle contains only numbers at most $50$, and if not, every cycle starts with a number at least $51$. Since the cycle representation is a uniformly random ordering, the first number is uniformly random. So, this happens with probability $1/2$, and the remaining $1/2$ the time we can open all the boxes.

More generally with $w$ wooden boxes and $s$ steel boxes, the probability of opening all the boxes equals the fraction of wooden boxes $\frac{w}{w+s}$.

Answer 2

If there are $50$ wooden boxes and $s$ steel boxes, as xnor has already said, the probability of unlocking all $s$ steel boxes (a "success") is $\frac{50}{50 + s}$. We can also prove this by induction on $s$.

Suppose box $1$ (with key $1$) is the first steel box. Given a random arrangement (the "original permutation") of the keys to the other $50 + (s-1)$ boxes, we can extend this to include the first steel box by placing key 1 in one of the $50 + s$ boxes at random (say box $\ell$), and then placing whatever key is in box $\ell$ in box 1. This extends a random original permutation of $50 + (s-1)$ boxes to a random permutation of $50 + s$ boxes.

What is the probability of success for the $50 + s$ boxes? Well, if key 1 gets placed in box 1 $\big(\frac{1}{50 + s} \ \text{probability}\big)$, we have no chance. Otherwise $\big(\frac{50 + (s-1)}{50 + s} \ \text{probability}\big)$, we succeed as long as the original permutation was a success $\big(\frac{50}{50 + (s-1)} \ \text{probability by induction}\big)$, since whenever we open box $\ell$, we get key 1, which we can use to open box $1$, and then we can continue as before. This gives a probability of $\frac{50+(s-1)}{50+s} \cdot \frac{50}{50 + (s-1)} = \frac{50}{50 + s}$. Plugging in $s = 50$ gives the $1/2$ result.