I had the idea to write another puzzle post because one of my previous posts was discussed briefly in a google groups thread. The post discusses the strategy that some prisoners trying to escape from an eccentric jailer should adopt and in the course of the discussion in the google groups thread, another puzzle about some prisoners was mentioned. This second puzzle asks for the strategy which some prisoners should adopt in order to escape from an improbable situation involving numbered lockers. I noticed that although the solution was discussed in the thread, the proof that the solution is optimal was not given.

I first came across the locker puzzle a few years ago and wondered how to prove that the solution was optimal. I discovered that a proof of optimality appeared in the *Mathematical Intelligencer*, 28(1):28-31, 2006. Since the argument for optimality is quite nice and doesn't seem to be obviously available on the web at the moment, I thought it might be worth writing about.

All of this is explained to the prisoners before they start the game. The question is, what strategy should they adopt and what is its probability of success?

At first it sounds like the prisoners' chances of success are pretty slim. After all, each prisoner's chance of finding the ticket with his number is only \(1/2\) and so if the prisoners adopt a strategy in which the events for each prisoner finding his ticket are independent then their total probability of success is a miniscule \( 1/2^{100}\). From this it is clear that the prisoners must adopt a strategy in which their individual successes are as far from independent as possible. The only trouble is, it seems difficult to arrange any significant deviation from independence given that the prisoners have no prior knowledge of the lockers' contents and are allowed no communication once they enter the locker room.

The key to this problem is to realise that the space of strategies is larger than it appears at first (to many people anyway). Recall that the prisoners are allowed to open the 50 lockers one by one. As a result a prisoner may choose which locker to open based on the contents (i.e. the ticket numbers) of any previous lockers he may have opened. Once we have the idea of using the contents of one locker to decide which locker to open next, a simple strategy suggests itself which we call the obedient strategy. In the obedient strategy a prisoner starts by opening the locker with his number on it; he examines the number of the ticket in this locker, if it is his number then he has succeeded so he can open any other 49 lockers, if not then he opens the locker bearing the number of the ticket he has just found. He continues like this until either he has found his own number or he has opened 50 lockers.

The question is, what chance of freedom do the prisoners have if they adopt this strategy?

The good news is that the prisoners have greatly increased their chances of success from \( 1/2^{100}\) to about 30%. Unfortunately this is still not great and the bad news is that unfortunately this is the best they can do as we shall now see.

Now that I've got thinking about puzzles I can't resist mentioning two other simple puzzles I like.

Another way to think about this is to associate a time to each ant which is how long it would take him to reach the end of the stick if he met no other ant. Then observe that when two ants meet (in the original version where they turn around) all that happens is that they swap the times. The solution is then clear.

As I finish writing this, I can't help wondering how the relativistically correct version of this puzzle might work out. Unfortunately I'm already running late and must head out but maybe I'll include a discussion in a future post!