The solution to the Jailer’s Revenge question is fairly lengthy, so I think it warrants a separate blog entry. Please refer to the original question as it too is fairly long.

Let’s firstly simplify the problem with smaller numbers, then scale it back up to 100 lockers and 100 prisoners. Let’s start with just 10 lockers and 10 prisoners.

The physical situation is unimportant; this is not a situational puzzle but a mathematical one. Indeed, there are variations on the scenario, such as putting people’s wallets in lockers. What is important is that the lockers and the prisoners are put into a one-to-one relationship. This is most easily achieved by numbering the lockers in an ordered sequence and numbering the prisoners in the same ordered sequence.

It doesn’t matter what the transformation is. In the original question, the lockers have already been numbered 1 to 100. If they were numbered in some other order we would have to number the prisoners using the same numbering system. So long as all locker labels are unique there is always a way of mapping the labels to a sequence of positive whole numbers. As the precise labels are unimportant and we wish to make the mathematics easier, we shall use the positive whole numbers.

So, the very first thing the prisoners have to do is to assign to each of them a number that corresponds to a locker number. The most obvious way is to list them alphabetically by name, but again, this is not important. The other thing the prisoners need to do is to remember the numbers of all the other prisoners. This may be mentally challenging but we assume this can be done. The original question stated that the card in each locker has a prisoner’s name on it, so the most obvious thing is to remember the alphabetical order of the prisoners and assign each a number in that order. Again, the important thing is that each name card is mapped onto a locker number – that there may be real prisoners or not is not important! The second important point is that such a mapping is done before the cards are placed within the lockers.

So let’s analyse the simplified 10-lockers problem. We have 10 lockers numbered 1 to 10. Inside each locker is a card with a name on it which has been coded with a number 1 to 10. Each prisoner also has a number 1 to 10 that corresponds to his name card. The problem is for each prisoner to locate the card with his name, and thus number, on it and remember which locker it is in. The astonishing thing is that there is a technique that partitions the lockers into cycles. Let’s see how this happens.

Here is a simple arrangement where the lockers are in their order 1 to 10 and the 10 numbered name cards have been randomly placed, one inside each locker.

Locker 1    2    3    4    5    6    7    8    9    10
Card    6    3    9    8    1    10    2    7    4    5

Now, pretend you are prisoner number 6. Recall that you have no choice in this; every prisoner is given a number and sticks to it. Indeed, once the cards have been placed in the lockers and the prisoners have been allocated their number the whole situation has been fixed and any algorithm proceeds without any further choices in the process.

The technique is that prisoner 6 opens locker number 6. Inside is card number 10, so he opens locker number 10. Inside is card number 5 so he next opens locker number 5. Inside is card number 1 so he opens locker number 1 and finds card number 6 – his card! To complete the cycle, this card would take him back to locker number 6, but he has already opened that one.

So this technique of opening the locker shown on each card will eventually lead to the prisoner’s own card. In our particular layout, this algorithm leads to a number of cycles. The one with the 6 in it is (10,5,1,6) and has a period of 4. All four prisoners that have one of those numbers will follow the same cycle and will find their number in the 4th locker they open.

Let’s see what happens to prisoner number 2. Following the same procedure he ends up in a cycle (3,9,4,8,7,2). In this case, he will find his card number in the 6th locker he opens. However, we now come to the part of the problem that states that each prisoner can only open half the lockers – 50 in the original problem and 5 in this simplified problem. So prisoner number 2 – and every prisoner in that cycle of period 6 – will not find his card by opening just 5 lockers.

The above random arrangement of cards and the method of opening the locker shown on each card, has resulted in two cycles, one of period 4 the other of period 6. In this particular case, the prisoners will lose because only 4 of them will find their card within 5 or less moves. However, the question has now been changed to finding how many random arrangements will yield cycles with periods of 5 or less. So long as there are no cycles of periods greater than half the lockers, every prisoner will find his name card and they will all be set free.

Before doing so, it is worth playing this game by yourself to see how it works. To remove any element of choice or bias, get a pack of playing cards and remove the court cards so that you have four suits of ten cards each. Lay the spades in sequence ace to 10; they will be our locker numbers. Then get the ten hearts, shuffle them, then lay them face down, one under each of the spades; these will be our number cards inside the lockers. Now you can pretend to be one of the prisoners. To show that choice is unimportant, you can shuffle the remaining 20 cards and pick one at random. That is your prisoner number and it is the first locker that you open, thereby revealing the card under the spade of the same number. Then just follow the algorithm. Once you have found one cycle, you can pick another prisoner number that has not yet been revealed. If you manage to find all the prisoner cards in 5 moves or less, the prisoners win; if not, they lose. It only takes a few seconds for each game so keep a tally of wins and losses. The experimental probabilities should be close to the theoretical ones we are about to calculate.

Back to the maths! Let us first note that there are 10! permutations of 10 objects in 10 lockers. What is the probability that those 10 numbered objects will form cycles of periods 5 or less? The calculation is actually easier if we look at the losing arrangements. The reason for this is that if an arrangement has a cycle of period 6 or more it can only have one such cycle, whereas if we look at cycles of periods 5 or less there can be multiple such cycles; this complicates the calculation without gaining any insights.

Firstly we have the ¹⁰C₆ combinations of 6 numbers from 10. Within that cycle of period 6 there are 5! permutations; because the arrangement is cyclic it is the same as 6 items round a circular table, hence is 5! and not 6!. Lastly, the remaining 4 objects can be in 4! permutations.

This yields a value of ¹⁰C₆.5!4! = 10!/6

So the probability that there is a cycle of period 6 is 10!/6*1/10! = 1/6

A surprisingly simple result. Similarly, the probability that there is a cycle of period 7 is just 1/7 and so on.

So, the probability that we have cycles of periods greater than 5 is just the sum 1/6 + 1/7 + 1/8 + 1/9 + 1/10 = 0.645634920, or about 64.6%.

But this means that the probability that our random arrangement actually has cycles of periods 5 or less is 0.35435080 or about 35.4%. Compare this with our intuitive answer of 1/2¹⁰, which is less than 0.1%.

So how does this scale up to 100 prisoners and 100 lockers. Well, we need to find the probability that we have cycles of periods 50 or less. Again, the easiest way is to calculate the probability that the prisoners lose and then find the complementary probability that they win. Extending our result for 10 lockers we get the expression for the probability of cycles of periods greater than 50 is:



So, the probability that our prisoners are set free is about 0.312 or just over 31%.

This is significantly higher than the 1/2¹⁰⁰ that we naively expected. But why does this happen? Our method imposes some structure on what appears to be random. This is similar to what happens with cellular automata; start with a random population and a simple rule and within just a few cycles we can see some order emerging. This happens because of feedback loops. In our case the feedback was created by numbering the name cards with the same numbers as those on the lockers.

Imagine if all the prisoners started simultaneously and the lockers formed a grid on the floor. They would all start on their numbered locker or cell. They would all be given the number hidden in the locker. If it is their own number they stand still, if it isn’t they move to the new locker number given to them. They all move at the same time. Carry on this sequence and you notice that some will stand still after a few moves. Slowly but surely they will all eventually stop moving once they have been given their own number. How many cycles has it taken for them all to have stopped moving? If it is 50 or less, the prisoners win. The prisoners still have a poor chance of winning, but it is a lot better than pot luck!

It should now be clearer as to how the jailer can guarantee that the prisoners stay firmly locked up – all he has to do is create a large cycle greater than a period of 50. Indeed, to be really frustrating he could create a cycle of period 100. However, there are a few traps lurking in having one long cycle – the possibility of creating another pattern! So the jailer must retain a random element, such as shuffling the name cards, but then split the cards into one pile larger than 50 cards. He then arranges those cards into one cycle; the simplest way is to look at the last card and place the first card into that numbered locker then proceed as a prisoner would do. This method removes any possible pattern that a human may unwittingly create. The remaining cards can then be distributed randomly; they don’t matter.

At this point we enter the realm of game theory, with player A being the jailer and player B the prisoners. Remember that if the prisoners fail once, the whole group fails, so player B must have an optimum strategy. The follow-the-numbers strategy is optimum for a genuinely random arrangement of cards. But, as noted in the original question, if the jailer’s assistant was really dumb or lazy (or both) and placed each prisoner name in alphabetical order, and if the prisoners chose their numbers according to their names, then the subordinate has unwittingly created 100 cycles of order 1 and the prisoners win without even breaking sweat. If the prisoners had chosen their numbers using a different criteria, then we’re back to the original algorithm. However, this is where the prisoners need to have an extra strategy that allows them to spot obvious patterns. This takes us beyond the scope of the original question but is interesting to contemplate whether there are strategies that B can take that improve on his 31% chance of success. Unfortunately, this seems unlikely and, given a rational player A, then player B is in deep trouble.

One corollary to this is how many lockers should the prisoners be allowed to open so that it becomes a fair game with a 50-50 chance of success? The answer turns out to be 60 lockers for a probability just below 0.5 and 61 lockers for it to be just above 0.5. This assumes, of course, a random initial layout. If, on the other hand, we’re back to the jailer’s revenge then he can always create a cycle of length one greater than the maximum allowed to each prisoner.



References

The Locker Puzzle by Eugene Curtin and Max Warshauer

The condemned prisoners and the boxes by Peter D. Taylor