19
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ nominee for the "weirdest prankster ever" award. :) $\endgroup$ – JLee Jul 13 '15 at 3:03
  • $\begingroup$ what if the prankster locked each boxes key in the same box? $\endgroup$ – Mauro Jul 13 '15 at 10:10
  • $\begingroup$ @Mauro "randomly places the 100 keys in the boxes, one key per box" $\endgroup$ – Angew Jul 13 '15 at 17:01
32
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ i want to up-vote this, but i don't understand it. i will come back when my brain stops hurting. $\endgroup$ – JLee Jul 13 '15 at 3:19
  • 1
    $\begingroup$ This looks really good. @JLee TL;DR - xnor orders the boxes so that wooden boxes appear at the start of each cycle, and cycles with no wooden boxes are written before cycles with wooden boxes. Then if (and only if) the first box of the first cycle is wooden, all cycles have a wooden box. $\endgroup$ – Lawrence Jul 13 '15 at 6:51
  • 2
    $\begingroup$ @Lawrence: If JLee is like me, then the part that you've explained is the non-brain-hurting part. The brain-hurting part is, how come there's exactly a 1/2 probability that the least greatest number is between 1 and 50? This answer says things like "each of the $n!$ such sequences represents one of the $n!$ permutations" and "the cycle representation is a uniformly random ordering" that really take some concentration to verify. (But they are indeed correct.) $\endgroup$ – ruakh Jul 13 '15 at 8:22
  • 1
    $\begingroup$ @ruakh Yes, a rather surprising result! Well done to xnor for transforming the problem from 100 (or indeed any number of) variables into just 1. If we ever end up with a best-of or essence-of series for puzzling, this question and answer deserves a spot in it. It keeps looking like there should be an overlooked wrinkle, but so far it's holding up well. $\endgroup$ – Lawrence Jul 13 '15 at 10:43
  • 2
    $\begingroup$ Very nice, but I'm stuck on Since the cycle representation is a uniformly random ordering, the first number is uniformly random. I cannot see how this is so... $\endgroup$ – frodoskywalker Jul 13 '15 at 13:17
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ cool! I had only known the proof using Knuth's cycle representation xnor mentioned, I'm glad you found a more intuitive proof $\endgroup$ – Mike Earnest Jul 15 '15 at 4:45
  • $\begingroup$ @MikeEarnest: Thanks for the comment. I don't know about more intuitive; I think xnor's proof is definitely more beautiful. But this proof, IMO, has less of a "how was I suppose to come up with THAT?" factor. $\endgroup$ – Tyler Seacrest Jul 16 '15 at 15:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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