probability - One Hundred Lockboxes of Wood and Steel

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

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}$.