To start with, assign each prisoner a different number between 1 and 100. Every prisoner should remember every other prisoner's number.

Don't think of names any more. Instead of thinking of each box as having a prisoner's name in it, think of it as having that prisoner's number in it. In fact, let's pretend that in addition to their name, each prisoner also wrote their own number on their piece of paper. This is a useful abstraction as we go forward.

If you open a box and look at the number inside of it, you can think of that as pointing you to another box. For example, if you opened box 61 and it had a the number 9 inside of it, then that would be pointing you to box 9. We can say that "box 61 is pointing to box 9." You could then open box 9, look at the number inside, and it would point you to another box.

So box A might point to box B, which might point to box C, which might point to box D, and so on. We see a sort of chain forming. It is guaranteed that eventually, one of the boxes in this chain will point back to A, forming a sort of chain loop.

This means, for example, that if you open box 61, then open the box that it points to, then open the box that that points to, and so on, you are guaranteed to eventually get to a box with the number 61 inside of it.

Now that we have these concepts, let's present a strategy for the prisoners choosing their 50 boxes. Each prisoner first opens the box with his number on it. Then, he open the box which that box points to, then to the box which that box points to, and so on, until he opens the box with his number (name) in it. We've already shown that it is guaranteed that the prisoner will eventually get to a box with his number in it if he starts on the box with his number on it; now we just need to find a way to guarantee that every prisoner will have to open at most 50 boxes before he gets to his number. This is where you come in with your switch.

Remember that all of these chains of boxes pointing to each other are actually loops. For example, if box 71 points to box 3, box 3 points to box 98, and box 98 points back to box 71, then this would be a loop containing 3 boxes. Or if box 44 had the number 44 in it, it would point to itself and be a loop of length 1. Every box is part of one loop, and one loop only.

Given this fact, it turns out that the number of boxes a prisoner will have to open is exactly equal to the number of boxes in his loop (by "his loop", we mean the loop containing his number). This is because he'll start with the box with his number on it, and end with the box with his number IN it, which is the box at the end of the loop since it points back to the starting box.

So if we can ensure that there are no loops longer than 50 boxes, then we've guaranteed that no prisoner will have to look through more than 50 boxes to find his number. Alternatively, if there are any loops of length 51 or longer when the prisoners start picking boxes, then they are guaranteed to lose.

There can be at most 1 loop among the 100 boxes that contains more than 50 boxes (if there was more than one loop with 51 or more boxes, this would mean there would have to be at least 102 boxes, which there are not). If there is no such long loop, then you don't need to switch any boxes. However, if there is such a loop, it's easy for you to break it up into two smaller loops using your switch. To do this, simply pick two boxes that are at opposite sides of the loop, and switch the numbers in them.

Let's go through a quick example on a smaller loop of size six. Let's say that Box 1 points to Box 2, which points to Box 3, which points to Box 4, which points to Box 5, which points to Box 6, which points back to Box 1. If you switch the contents of Box 3 and Box 6 (which are on opposite each other in the loop), then we'll now have two rings of size 3 (Box 1 points to Box 2, which points to Box 3, which newly points to Box 1. And Box 4 points to Box 5, which points to Box 6, which newly points to Box 4).

So we are able to turn this long loop into two smaller loops of half the size, which are each guaranteed to each contain 50 or fewer boxes. Now we can be sure there are no loops that contain more than 50 boxes, and so when the prisoners follow their box-choosing strategy, they are guaranteed to open the boxes with their own numbers (names) in them.

Don't think of names any more. Instead of thinking of each box as having a prisoner's name in it, think of it as having that prisoner's number in it. In fact, let's pretend that in addition to their name, each prisoner also wrote their own number on their piece of paper. This is a useful abstraction as we go forward.

If you open a box and look at the number inside of it, you can think of that as pointing you to another box. For example, if you opened box 61 and it had a the number 9 inside of it, then that would be pointing you to box 9. We can say that "box 61 is pointing to box 9." You could then open box 9, look at the number inside, and it would point you to another box.

So box A might point to box B, which might point to box C, which might point to box D, and so on. We see a sort of chain forming. It is guaranteed that eventually, one of the boxes in this chain will point back to A, forming a sort of chain loop.

This means, for example, that if you open box 61, then open the box that it points to, then open the box that that points to, and so on, you are guaranteed to eventually get to a box with the number 61 inside of it.

Now that we have these concepts, let's present a strategy for the prisoners choosing their 50 boxes. Each prisoner first opens the box with his number on it. Then, he open the box which that box points to, then to the box which that box points to, and so on, until he opens the box with his number (name) in it. We've already shown that it is guaranteed that the prisoner will eventually get to a box with his number in it if he starts on the box with his number on it; now we just need to find a way to guarantee that every prisoner will have to open at most 50 boxes before he gets to his number. This is where you come in with your switch.

Remember that all of these chains of boxes pointing to each other are actually loops. For example, if box 71 points to box 3, box 3 points to box 98, and box 98 points back to box 71, then this would be a loop containing 3 boxes. Or if box 44 had the number 44 in it, it would point to itself and be a loop of length 1. Every box is part of one loop, and one loop only.

Given this fact, it turns out that the number of boxes a prisoner will have to open is exactly equal to the number of boxes in his loop (by "his loop", we mean the loop containing his number). This is because he'll start with the box with his number on it, and end with the box with his number IN it, which is the box at the end of the loop since it points back to the starting box.

So if we can ensure that there are no loops longer than 50 boxes, then we've guaranteed that no prisoner will have to look through more than 50 boxes to find his number. Alternatively, if there are any loops of length 51 or longer when the prisoners start picking boxes, then they are guaranteed to lose.

There can be at most 1 loop among the 100 boxes that contains more than 50 boxes (if there was more than one loop with 51 or more boxes, this would mean there would have to be at least 102 boxes, which there are not). If there is no such long loop, then you don't need to switch any boxes. However, if there is such a loop, it's easy for you to break it up into two smaller loops using your switch. To do this, simply pick two boxes that are at opposite sides of the loop, and switch the numbers in them.

Let's go through a quick example on a smaller loop of size six. Let's say that Box 1 points to Box 2, which points to Box 3, which points to Box 4, which points to Box 5, which points to Box 6, which points back to Box 1. If you switch the contents of Box 3 and Box 6 (which are on opposite each other in the loop), then we'll now have two rings of size 3 (Box 1 points to Box 2, which points to Box 3, which newly points to Box 1. And Box 4 points to Box 5, which points to Box 6, which newly points to Box 4).

So we are able to turn this long loop into two smaller loops of half the size, which are each guaranteed to each contain 50 or fewer boxes. Now we can be sure there are no loops that contain more than 50 boxes, and so when the prisoners follow their box-choosing strategy, they are guaranteed to open the boxes with their own numbers (names) in them.

Please sign-in to write a comment.