Prisoners in Hats — alaricstephen.com

Carrying on with the theme of prisoner puzzles (I now have more than one lesson’s worth of prisoner puzzles. I guess I'm going to have to do something different for the Christmas lessons with my AS students now that I've spoiled them all on here) I present two related puzzles. The first is infamous while the second is less well known.

There are four prisoners buried up to their neck in sand. Here’s a diagram of the setup with noses showing the direction each prisoner is facing:

Apologies for the quality of the photo. This article was written during the Worcester Music Festival and with the help of several pints of Old Rosie

The prison warden shows them 2 white hats and 2 black hats and places the hats onto the prisoners as shown in the diagram above. There is a wall separating one of the prisoners from the others. Prisoners can't turn their heads but can see all of the people in front of them. When the warden shouts go, the prisoners have a minute to guess the colour of the hat on their own head. If someone guesses correctly they all go free, but if someone guesses incorrectly then everyone is immediately executed. Any attempt to communicate anything other than a genuine guess also leads to execution.

There is a strategy to win. Who guesses correctly and what is the logic?

Hints below.

Hint 1, although prisoner number 2 can see two hats and so has the most information, he isn't the one to make the call.

Hint 2, after half a minute of no one guessing, what would that tell you?

It is prisoner 3 that guesses correctly. If prisoners 3 and 4 had had the same colour hat then prisoner 2 would see them both and so would know that he had the other colour. Because he hasn't said anything they must have different coloured hats. So because number 3 can see the white hat on number 4 he knows he must have black.

The surprising thing about this puzzle is that it isn't the person with the most initial information that solves it; a silence actually communicates something useful.

OK, that is the classic problem dealt with. I want to introduce an extension which I heard in Oxford when I went up for the interviews. There were a whole bunch of mathematicians around and we were posed this problem where you can keep improving on your answer. I'll take you through the typical thought process.

100 prisoners are buried up to their necks in sand, all facing the same way, so prisoner 1 can see prisoners 2 onwards and so on. Each wears either a black hat or (well, xor) a white hat, but this time there is no guarantee that there are an equal number of each colour.

The warden starts with prisoner number 1 and asks “white or black?” The prisoner responds with their guess as to the colour of their own hat and if they are correct they get to live, but if they are wrong then they are shot. Either way the warden then moves on to prisoner number two. The same thing will play out the whole way along the line, but before this process begins the prisoners are told the whole situation and are allowed to come up with a plan to save as many people as possible. Now on average half will survive anyway, so for ease of language I'm going to be talking about how many we can definitely save.

Your first challenge: come up with a strategy that definitely saves 50 people.

...

So hopefully that wasn't too hard. If prisoner 1 says the colour of the hat in front then prisoner 2 will know their colour and can say it going free. Notice that number 2 can't say the colour of 3's hat because then they won't be able to save the self. So in effect the prisoners pair up with the odd numbered ones saving the even ones. OK, new challenge, by grouping the prisoners into threes, save 2 out of 3. You will be using logic similar to the first prisoners with hats puzzle. I advise giving it a few minutes thought, it is quite satisfying.

Here's how it works. No one can see number 1's hat so we can't save that person, which means we will have to focus our efforts on the other two. But how can one person give two pieces of information with one bit of data (no cheating by trying to put in a delay in your answer or saying something which isn't black or white)? The key here is to realise that number 2 has an extra piece of information: he can see 3's hat colour. If 1 says white if 2 and 3 have the same colour hats and black if they have different colours then prisoner 2 can look at 3 and either pick the same colour or not as instructed.

Since 100 doesn't divide by 3 then the last person is on their own, but this saves 66 for sure. Can we improve? We can and before I give you the optimal solution I want to give you the solution that I came up with when I was 17. I saved 93 prisoners.

The idea was that if the total number of black hats was known then everyone else can be saved. For instance if you know there are 37 black hats left and you can see 36 then you know you have a black hat. Using the first 7 people is enough to encode the number of black hats in the other 93 in binary (since 2^7=128). It is neat, but not a perfect solution yet.

Surprisingly you can save 99 prisoners for sure (and have a half chance at getting all 100). You need to realise that the total number of black hats is overkill, all you need is the parity of that number: an odd number of black or an even. So we could have a perfect solution if the first prisoner says white for and even number of white hats in the other 99. For example if you are the second prisoner and you hear black then you know that there is an odd number of white hats. if you can see an even number of white hats then you must have a white hat. Because the next prisoner can hear your response they can keep a mental checklist of whether they should see an odd or even number of white hats when it gets to their turn. Very neat.