Opening Boxes

Probability Level 3

Alice and Bob are in a room with 100 boxes. The boxes are labeled 1, 2, ..., 100. Bob has 100 sheets of paper, also labeled 1, 2, ..., 100. He randomly puts one sheet of paper into each box.

Alice may start by opening any box of her choice.

After opening a box and finding paper $k$ :

If box $k$ is unopened, Alice will open box $k$ and repeat this process.
If box $k$ is open, Alice will stop.

What is the probability that Alice will open all of the boxes? When your answer is of the form $\frac{p}{q}$ , where $p$ and $q$ are positive, coprime integers, input $p+q$ .

The answer is 101.

3 solutions

Ivan Koswara
Jul 18, 2015

I'm sure there is a more elegant solution that this, but I can't find it at the moment.

We change the rules slightly:

Suppose the first box is numbered $a$ , containing the paper $b$ , and assume $a \neq b$ Suppose box $b$ contains the paper $c$ . Immediately swap the contents of the two (so box $a$ contains paper $c$ and box $b$ contains paper $b$ ), and kick away box $b$ . Thus now we only need to look at box $a$ .

Suppose there are $n$ boxes, and box $a$ doesn't contain paper $a$ . Then after kicking one box, we're left with the identical(!) situation on $n-1$ boxes. This allows induction.

The only way to open all boxes is if we kick all the boxes except for box $a$ . If there are $n \ge 2$ boxes, the probability that we will kick at least one box is simply $\frac{n-1}{n}$ (the probability that box $a$ doesn't contain paper $a$ ). Thus the probability of opening all boxes is the probability of opening some box, for all of $n = 100, 99, 98, \ldots, 2$ , multiplied together. This gives $\frac{99}{100} \cdot \frac{98}{99} \cdot \ldots \cdot \frac{1}{2} = \boxed{\frac{1}{100}}$ .

Moderator note:

There actually isn't a need to change the rules. The main observation is that "the game ends when we find the paper marked $a$ ".

If there are $n$ boxes left, and none of the previous boxes have the paper marked $a$ , then the probability that the next box doesn't have the paper marked $a$ is $\frac{n-1}{n}$ . Thus, the probability that we don't find the paper marked $a$ for 99 boxes, is just

$\frac{99}{100} \times \frac{98}{99} \times \ldots \times \frac{1}{2}$

Maggie Miller
Jul 17, 2015

The arrangements of papers in boxes uniquely determines an element from the symmetric group $S_{100}$ , which sends $n$ to $k$ when box $n$ contains paper $k$ . Alice will open all the boxes if and only if this element of $S_{100}$ is a cycle of length $100$ . There are $99!$ such elements, and $100!$ elements altogether in $S_{100}$ . Therefore, the probability that Alice will open all the boxes is $\frac{99!}{100!}=\frac{1}{100}$ , so the answer is $\boxed{101}$ .

Does this cover the chance that paper k is in box k ? If that's the case, then it is indeed $1/100$ . But does it also cover the chance that paper k is in box n paper n in box k ? Then you will have to take care of cycles 2-98.

Anthony Pham - 5 years, 11 months ago

When paper $k$ is in box $n$ and vice versa, that case is still covered - Alice can't open all the boxes because if she opens box $k$ , she could have only opened box $k$ and $n$ . The corresponding element in $S_{100}$ has a cycle of length 2, so it isn't a cycle of length 100.

Similarly, when paper $k$ is in box $k$ , Alice can't open all the boxes because if she opens box $k$ , she couldn't have opened anything else. The corresponding element of $S_{100}$ fixes a number ( $k$ ), so isn't a cycle of length 100.

So, we count both of these cases as cases where Alice doesn't open all the boxes. The cases with cycles 2-98 are similar! Hope that helps.

Maggie Miller - 5 years, 11 months ago

Nobody understanding the answer

Adarsh Mahor - 5 years, 11 months ago

Yeah, it's a bit of college-level algebra, but it is very slick. Luckily, Ivan has uploaded a more accessible answer! :)

Maggie Miller - 5 years, 11 months ago

You could make the solution by accessible by explaining why
- There are 100! permutations of 100 elements
- There are 99! permutations that involve a 100 cycle

Yes, the "correct" setting is in terms of permutation groups, but it isn't necessary for someone to understand group theory, in order to solve this problem.

Calvin Lin Staff - 5 years, 11 months ago

Radhika Saithree
Jul 19, 2015

There is a good chance that the paper won't be in the right box (99/100 chance, I think). But imagine her opening all the boxes... if she opens one and it is wrong, she goes to the next one, and then the next one and the next one till she opens the last box. But what if she does find a right after opening box 99? or box 38? or box 47? and so on... So there is a 99% chance that she will find the right one in one of the boxes between box one and box hundred. Meaning 1/100 chance of opening ALL of the boxes and ALL of them are wrong.

1 + 100 = 101.

Note: this is just my guess at what the solution would be. It may not be an entirely accurate response/way to solve it :)

This is right - great intuition! :)

Maggie Miller - 5 years, 11 months ago

Opening Boxes

The answer is 101.

3 solutions

Moderator note:

0 pending reports