THE PRISONER'S BOXES

You are the janitor at a prison with 100 prisoners locked in separate, soundproof and windowless cells.

You watch one day as the warden brings the prisoners out to a central room where there are 100 boxes laid out, labeled 1 through 100. He hands each prisoner a slip of paper and a pen, and asks everyone to write their name on their slip and hand it back to him. All the prisoner's have different names.

The warden then makes a proposition to the prisoners. He will put them back in their cells and will put each of the 100 slips of paper into a different box. The prisoners will then be brought out one by one in a random order. When a prisoner comes out, he will get to open 50 boxes. He doesn't need to pre-select which boxes he'll open; he can choose as he goes along. He is also not allowed to rearrange the boxes or the names as he does this.

If any of the 50 boxes he opens contains the slip with that prisoner's name on it, then that prisoner "passes" the test. He will be sent back to his cell, all of the boxes will be closed, and the next prisoner will be brought out. However, if any prisoner opens 50 boxes and none of them contain his name, then all 100 prisoners will be executed. Note that prisoners have no way of passing information on to any of the prisoners who go after them.

If all of the prisoners are able to "pass" the test, then they will all be set free, and you'll receive a big promotion.

Luckily for the prisoners, the warden is going to let you help them in the following way. After he's put all of the names in the boxes, he will bring you into the room, let you look at all the names in all the boxes, and then, if you choose to, switch two names with each other. For example, you could switch the names in boxes 35 and 77. You are only allowed to make one switch.

After you help with this task, you will be sent out of the prison and will not be able to communicate with the prisoners.

Before this strange game begins, you get to meet with the prisoners to discuss a strategy. 

This strategy must have two parts:

1. How do you decide which names to switch, if any at all?
2. How does each prisoner decide which 50 boxes he will open?

What plan do you come up with to ensure that the prisoners will all go free?

[[HINT]]>>

     This is a tough riddle. Here are a few hints:

• If you assign each prisoner a different number between 1 and 100, you can correlate each prisoner with one of the 100 boxes in a manner unrelated to the slips of paper. This could help with the prisoners' process for deciding which boxes to open.
• You need to ensure that certain combinations of names/boxes do or do not arise as the warden puts the slips in the boxes in order to make sure that the prisoners' box-choosing strategy works. You can do this with your switch (if you choose to make one).]]

SOLUTION: 

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.

Please share your views>>