## Prisoner Problem

The jail is getting rather crowded, and the jailor is thinking about setting some of the prisoners free. However they have to solve a challenge. If they fail, then they go back to their cells, and another group of prisoners will get a go. The challenge goes like this.

Ten prisoners will be selected, and have the challenge explained to them. They are allowed to confer at this stage, and plan their strategy. Then comes the challenge...

The prisoners will be lined up in a single file, all facing the same direction. The prisoner at the back can see all nine prisoners in front of him. The prisoner at the front cannot see any of the other prisoners, since they are all behind him. The prisoners standing in the rest of the line will only be able to see the prisoners in front of them, not the ones behind them.

Once the prisoners are standing in line, each prisoner will have a hat placed on their head. The hat will be either black or white. The choice of colour in each case is completely random. No prisoner can see the colour of their own hat. A prisoner can see the colour of the hats worn by any prisoners standing in front of him, but cannot see the colour of any hats worn by prisoners standing behind him.

Each prisoner then has to guess the colour of the hat they are wearing, and speak their choice out loud. They can only speak a single word, either 'white' or 'black'. The first prisoner to guess must be the prisoner standing at the back of the line. Then the prisoner in front of him, and so on. The last to speak will be the prisoner standing at the front of the line.

The jailor knows that this is a tough challenge. He will allow a maximum of one mistake, so long as the other nine guesses are correct. In which case, all ten prisoners will be released. However if there is more than one mistake, all the prisoners will be returned to their cells.

What is the best strategy the prisoners can adopt? What are their chances of getting free?

There are no tricks. Just mathematics.

The answer is given on the next page.

The surprising answer to this problem is that the prisoners will always go free, so long as they follow the correct strategy.

The prisoner at the back, who has to go first, cannot know whether they have a white or a black hat on their head. So, as it makes no difference whether they say white or black, they use their go to enable all the other prisoners to guess correctly, and thus all the prisoners go free. It works like this.

The prisoner at the back looks at the row of prisoners in front of him, and counts the number of black hats that he can see. If it is an odd number, he says 'black' and if it is an even number he says 'white'. He has a 50% chance of being correct as far as his own hat is concerned.

The prisoner in front of him counts how many black hats HE can see, and to this number he adds 1 if the prisoner behind him has said 'black'. If this number is odd, the second prisoner says 'black' since that will be the colour of his hat; however if the number is even, he should say 'white' and again this will be the colour of his hat.

Each prisoner in turn counts the number of black hats they can see in front of them, adds the number of times they have heard 'black' spoken, and they then say 'black' if the number is odd, and 'white' if the number is even.

Every prisoner will be able to guess correctly the colour of the hat they are wearing, apart from the prisoner at the back who guesses first. They have a 50% chance of being right. The jailor's conditions will have been met - not more than one mistake will have been made - and all the prisoners will go free.

Another way of thinking about the solution could be put this way... suppose the prisoner at the back can see 5 black hats in front of him, and he therefore says 'black' since 5 is an odd number. The prisoner in front of him happens to be wearing a white hat, and so he will also see 5 black hats in front of him. 5 plus 1 (the prisoner behind him said 'black') is an even number, therefore he guesses - correctly - that he is wearing a white hat. This will continue until we get to a prisoner who is actually waering a back hat. They will only see 4 black hats in front of them (they are wearing the 5th one!) and so they will add 4 and 1, which is an odd number, and correctly guess that they are wearing a black hat.