One Hundred Lockboxes, Variant

Question

You have one hundred lockboxes, fifty made of steel, fifty made of wood, and a key for each box.

A prankster breaks into your house and distributes the keys among the boxes. He places each key in a random box independently of the other keys, so that some boxes may receive multiple keys while others have none. He then closes 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?

Bonus: What if you had $n$ lockboxes in total, $k$ of which were wooden?

---

Remarks: This is a slight variation of a question I previously asked. In that puzzle, the prankster also randomly placed the keys in the boxes, but did so in a way that no two keys were put in the same box. Will his change in behavior increase your chances of being able to open all the boxes, or decrease them?

Answer 1

I'm late to the party but I love this problem so I'm adding my own solution. Consider the following variant of the variant:

The prankster has $n$ Ziploc bags. He places the $n$ keys in the bags anyway he wishes, potentially maliciously. Some bags could receive multiple keys, while other bags receives none. He then randomly places exactly one bag in each lockbox, and closes the box. What is the probability we will be able to open all the boxes?

This generalizes the variant, since if he wants the prankster could place each key in a random bag independently, and then the extra permutation when placing the bags in the boxes is redundant.

Yet even if the prankster does not act randomly on the keys in bags step, I claim the probability of opening the boxes (a "success") is still $\frac{k}{n}$.

Proof

We will use induction on the number of boxes.

If there is no empty bag, then there must be one key per bag, and this reduces to the original problem.

If there is an empty bag, then take a particular empty bag $E$ and suppose the prankster randomly places $E$ first, and then randomly places the other bags. Given a fixed location for bag $E$, we can use induction to calculate the probability of success. This is because the box with $E$ in it, and its key, has no effect on whether we can open all the boxes. We can just remove the box containing $E$ and pretend its key magically disappears, and we are left with a random permutation of the other $n-1$ bags in the other $n-1$ boxes. If and only if this $n-1$ box arrangement is a success will we have success with the bigger arrangement.

• If $E$ is in a steel box (which happens with probability $\frac{n-k}{n}$), then the probability success after removing $E$ by induction is $\frac{k}{n-1}$.

• If $E$ is in a wooden box (which happens with probability $\frac{k}{n}$), thent he probability of success after removing $E$ by induction is $\frac{k-1}{n-1}$.

We can then compute the probability of success including $E$ as

$= \frac{n-k}{n} \cdot \frac{k}{n-1} + \frac{k}{n} \cdot \frac{k-1}{n-1}$

$= \frac{(n-k)k + k(k-1)}{n(n-1)}$

$= \frac{nk - k}{n(n-1)}$

$= \frac{k(n-1)}{n(n-1)} = \frac{k}{n}$

Answer 2

This solution is for revenge! Warning: it's long and assumes mathematical maturity. I don't think anyone will even read it all. I seriously hope someone else posts an elegant solution. But I had to post this, because this problem is Putnam 2013 B5, which I failed to solve during the test despite working on it for an hour. I never looked at a solution, so this post is my way of getting revenge.

Call a set $C$ of stone boxes closed if all the keys for boxes in $C$ are locked inside boxes in $C$. A box is forever unopenable iff it lies in a closed set. We want to find the probability that there exists at least one nonempty closed set. Letting $S$ denote the set of stone boxes, we want to calculate

$$ \Pr\left[\bigcup_{C\subseteq S, C\neq \emptyset} C\text{ is closed}\right].$$

Using the principle of inclusion-exclusion, this equals

$$ \sum_{F} \Pr[\text{All sets in $F$ are closed}]\cdot(-1)^{|F|-1}$$

where $F$ ranges over all nonempty collections of nonempty subsets of $S$.

At first this sum looks hopeless: it is a sum over $2^{2^{|S|}-1}$ terms, each of which has a complicated probability. But we can force almost all of the terms to cancel, using a clever bijection.

Let $F$ be a collection of nonempty subsets of $S$. Call $F$ weird if $F$ contains a pair of non-nested sets. Define the smallest pair of a weird set $F$ to be the pair of sets $C$, $D$ in $F$ minimizing $C \cup D$, breaking ties in some arbitrary but consistent way.

Define the twin of a weird set $F$ as follows. Let $C$, $D$ be $F$'s smallest pair. Then the twin of $F$ is obtained by taking $F$ and toggling whether it contains $C \cup D$. With mild casework, one can show that the twin of the twin of $F$ is always $F$ itself.

So, the twin relation partitions the weird sets into twins. Let $F$ and $F'$ be twins. Let $C$, $D$ be $F$'s smallest pair. It follows from the definition of closed that if $C$ and $D$ are closed, then so is $C\cup D$. Therefore, all sets in $F$ are closed iff all sets in $F'$ are closed. Also, it follows from the definition of twin that one of $F$, $F'$ is exactly one element larger than the other. Therefore, the terms for $F$ and $F'$ cancel in the gigantic sum above.

This cancellation cancels out all terms in the gigantic sum using a weird set $F$. What is left? The sets $F$ which are not weird, i.e. where all pairs of sets in $F$ are nested. In other words, the sum now ranges over nonempty collections of nested nonempty subsets of $S$. We rewrite the sum:

$$ \sum_{S \supseteq C_0 \supset C_1 \supset \dots \supset C_k \neq \emptyset} \Pr[\text{$C_0, C_1, \dots, C_k$ are all closed}]\cdot(-1)^{k}$$

where $C_0 \supset C_1 \supset \dots \supset C_k$ ranges over all nonempty sequences of nested nonempty subsets of $S$.

Define the weight of a set $C\subseteq S$ as follows.

$$ weight(C) := \sum_{C \supset C_1 \supset \dots \supset C_k \neq \emptyset} \Pr[\text{$C_1, \dots, C_k$ are all closed | $C$ is closed}]\cdot (-1)^k$$

I claim that the weight of a set $C$ equals $1$ if $|C|=1$, and $0$ otherwise. The proof is by induction on the size of $C$. The base case, $|C|=1$, is a sum over one term which equals $1$. For the inductive step, assume the statement is true for all $|C|<n$, and consider a set $C$ of size $n$. In the sum in the definition of the weight above, we isolate the term where $C_1, ..., C_k$ is the empty sequence. This term adds $1$ to the overall sum. The rest of the terms all contain a set $C_1$. We rewrite the sum thus:

$$ weight(C) = 1 + \sum_{C\supset C_1 \neq \emptyset} \sum_{C_1 \supset \dots \supset C_k \neq \emptyset} \Pr[\text{$C_1, \dots, C_k$ are all closed | $C$ is closed}]\cdot (-1)^k $$

$$= 1 + \sum_{C\supset C_1\neq \emptyset} \Pr[\text{$C_1$ is closed | $C$ is closed}]\sum_{C_1 \supset \dots \supset C_k \neq \emptyset} \Pr[\text{$C_2, \dots, C_k$ are all closed | $C_1$ is closed}]\cdot (-1)^k$$

$$ = 1 + \sum_{C\supset C_1} \Pr[\text{$C_1$ closed | $C$ closed}] \cdot (-weight(C_1)) $$

By the induction hypothesis, all $weight(C_1)$ terms are zero except the ones where $|C_1|=1$. Thus, the sum equals

$$ = 1 + \sum_{\{s\}\subset C} \Pr[\text{$\{s\}$ closed | $C$ closed}] \cdot -1 $$

$$ = 1 + \sum_{\{s\}\subset C} -\frac{1}{|C|} $$

which is zero. This completes the inductive step, finishing our calculation of the weight function.

Now, what was that sum we wanted to evaluate again? Here it is:

$$ \sum_{S \supseteq C_0 \supset C_1 \supset \dots \supset C_k \neq \emptyset} \Pr[\text{$C_0, C_1, \dots, C_k$ are all closed}]\cdot(-1)^{k}$$

This sum ranges over all nonempty sequences of nested subsets of $S$. Since the sequence $C_0, C_1, \dots, C_k$ must be nonempty, it must always contain a set $C_0$. We rewrite the sum, in a similar way to our proof of the inductive step of the weight function.

$$ \sum_{S \supset C_0 \neq \emptyset} \sum_{C_0 \supset C_1 \supset \dots \supset C_k \neq \emptyset} \Pr[\text{$C_0, C_1, \dots, C_k$ are all closed}]\cdot(-1)^{k}$$

$$ = \sum_{S \supset C_0 \neq \emptyset} \Pr[\text{$C_0$ is closed}] \sum_{C_0 \supset C_1 \supset \dots \supset C_k \neq \emptyset} \Pr[\text{$C_1, \dots, C_k$ all closed | $C_0$ closed}]\cdot(-1)^{k}$$

$$ = \sum_{S \supset C_0 \neq \emptyset} \Pr[\text{$C_0$ is closed}]\cdot weight(C_0) $$

By our calculation of the weight function, all terms are zero except those where $|C_0| = 1$. Thus, this equals

$$ \sum_{\{s\} \subseteq S} \Pr[\text{$\{s\}$ is closed}] $$

This, finally, is an easy sum to calculate. Let $n$ be the total number of boxes. Then the sum equals

$$ \sum_{\{s\} \subseteq S} \frac{1}{n} $$

$$ = \frac{|S|}{n} $$

Therefore, the probability that there exists at least one closed set is $|S|/n$. Therefore, putting $k$ as the number of wooden boxes, the probability that all boxes are openable is $k/n$. In conclusion, this variant has the same answer as the original question.

Answer 3

In the other lockbox problem, where the assignment of keys to boxes was a random permutation, you could use a clever representation of permutations to show that $\frac{k}n$ of the permutations had a wooden box in all of their cycles. In this case, we do a similar thing, using a clever representation of arbitrary functions from $\{1,\dots,n\}$ to $\{1,\dots,n\}$. First, we need some preparation.

Let $[n]$ be shorthand for $\{1,\dots,n\}$. Given a function $f:[n]\to[n]$, let a cycle of $f$ be a list $x_0,x_1,\dots, x_n$, where $f(x_{k-1})=x_k$ and $f(x_n)=x_0$. Every function has at least one cycle, since the list $1,f(1),f(f(1)),\dots$ must have a repeat. There are many ways to write the same cycle, for example, 1,2,3,4,5 is the same as 5,1,2,3,4 and 2,3,4,5,1. We will assume a cycle is always written so the first number $x_0$ is the smallest number in the cycle.

So, what is this clever representation of $f$? It will be a list $L$ of $n$ numbers, where every list element is an integer between $1$ and $n$. $L$ is given by the concatenation of two lists, $P$ and $S$ (for "prefix" and "suffix").

The entries of $P$ will consist of the numbers which are in some cycle of $f$. Specifically, to find $P$, find all of the cycles of $f$. Order the cycles in decreasing order of their first element, then concatenate them all together to one list.

To find $S$, first find $P$, then use the following algorithm:

let S = [], an empty list
let U = the set of numbers in [1,...,n] which are not in P
while U is nonempty:
    let y = smallest element of U which is not of the form f(u) for some u in U
    add f(y) to end of S
    remove y from U

Because of how $y$ is chosen each step, we know that if $y_{last}$ is the last element removed from $U$, then $f(y_{last})$ will be in $P$. This means that the first element of $S$ appears in $P$.

This encodes $f$ as a list $L$. What is surprising is that you can decode a list $L$ to a unique function $f$. This means the encoding process is a bijection from functions to lists.

How does decoding work? Given $L$, we can recover $P$ and $S$ by letting $P$ be the largest prefix of $L$ whose entries are all distinct, and $S$ be the rest of $L$. This allows us to retrieve the cycles of $f$, since every entry of $P$ which is smaller than the ones before it will be the start of a cycle. We now know $f(x)$ for every $x$ in a cycle. To find the other unknown values, let $x$ be the smallest unknown number not appearing in $S$, set $f(x)$ to be the last element of $S$, then remove the last element of $S$. Repeat until $S$ is empty, at which point $f(x)$ will be known for all $x$.

We now use this encoding to solve the puzzle. Number the boxes $1$ to $n$ so that boxes $1$ to $k$ are wooden. Let $f(x)$ be the number of the box containing the key to box number $x$, and let $L$ be the encoding of $f$. We will be able to open all the steel boxes if and only if every cycle of $f$ contains a wooden box. This occurs if and only if the first entry of $L$ is in $\{1,\dots,k\}$. Since the encoding is a bijection from functions to lists, and $f$ is a random function, it follows that $L$ is a random list. This means that the first entry of $L$ has a $\frac{k}{n}$ chance of being in $\{1,\dots,k\}$, so the probability desired is $\frac{k}n$.

Answer 4

This solution is heavily inspired by those of Tyler Seacrest and Mike Earnest.

---

Consider a placement of keys in boxes. Given a box, one can trace back the box that contains its key, the box that contains that boxes's key, and so on. This chain must eventually loop in a repeating cycle, though that cycle might not contain the initial box. Let's say cycle boxes are those within a cycle, and path boxes are the rest.

From tracing back, we see that opening any box reduces to opening some cycle box via some chain of keys. Moreover, no path box lets you open a cycle box, since the key to a cycle box lies within that cycle. So, path boxes are totally vestigial: whether you can open all boxes doesn't change if you remove all path boxes.

Now, note that restricting to the cycle boxes and their keys yields a uniformly random permutation, reducing to the original problem. This is because if the key locations of the path boxes are fixed, the overall assignment is completed by placing each cycle box's key into a distinct cycle box.

We showed that the probability of opening all boxes for a permutation of keys equals the probability that a random box is wooden. So in this problem, all boxes can be opened with the same probability that a random cycle box is wooden. Since being a cycle box or not isn't influenced by material, this equals the fraction of wooden boxes $k$/$n$.

Answer 5

My attempt :

We don't have to take in count the wooden boxes' keys. Each time the prankster pick a steel box's key, there is $50$% chances that he put it into a wooden box. Since there's $50$ keys, the odds that all the steel boxes' keys are in wooden boxes is $(\frac{1}{2})^{50}$.

Bonus :

$s = n-k$
$(\frac{k}{k+s})^s$