# The sadistic executioner (a.k.a the 100 prisoners) [duplicate]

100 prisoners are sent into a room to hear the warden say: "tomorrow I will line you up and put a hat on your head. The hat can be red, green, yellow, …" and he goes on enumerating colors. He then adds: "The executioner will then start from the back of the line and run up to the front, and to every prisoner he will ask what the color of his hat is. If the prisoner guesses the color correctly then he is freed, but if he gets it wrong he will be killed right away.

The following days, the prisoners are lined up, and the warden puts a colored hat on their head. Then, the executioner starts asking question. The unlucky prisoner at the back of the line guesses wrong and is killed. But by some magic, all the other prisoners guess the color of their hat correctly.

How did they do?

PS: I apologize for my English

## marked as duplicate by klm123, Gilles, GOTO 0, mdc32, Joe Z.Nov 16 '14 at 23:41

• How many different colors are there? – pacoverflow Nov 15 '14 at 19:02
• @pacoverflow There are N colors, N is an integer greater or equal to 1. The point is, the prisoners know the colors, but they don't know how many hats of each color there will be. The announced colors could be "green, red and black" but on the next day, only red and green hats are placed on the head of the prisoners – qdii Nov 15 '14 at 19:13
• There can't be N colours if they're being named. There are only (approximately) 1800 named colours and at least 1600 are variant shades. In reality, there are less than 30 clearly discernible colours before you end up in an argument over whether a colour is purple or mauve, beige or yellow, etc. – Richard Nov 16 '14 at 0:18
• This looks similar to puzzling.stackexchange.com/questions/2261/of-men-and-hats – user5352 Nov 16 '14 at 0:48
• A funny, if more mathematically involved variant of this puzzle: suppose there are infinitely many mathematicians in a row, wearing hats of colours from $1$ to $N$ (finitely many). Each mathematician can see the colours of hats of all people in front of him (and no one else). Now, it's not very hard to find a strategy that lets almost all of them survive (as in, mean survivability tends among first m mathematicians tends to $1$ as $m$ tends to infinity), but assuming axiom of choice, there is a strategy that allows all but finitely many to survive. – tomasz Nov 16 '14 at 1:25

This is a fantastic puzzle, one of the best I have had to solve, so give yourself time to think it over. It took me a month to come to the solution.

To make you guys understand the solution, I will first demonstrate it in a particular case where there are just two colors. I will then expand it to N colors.

Preliminary logical deduction:

The fact that the prisoners are in line adds nothing to the puzzle. Once the first prisoner has talked, there is no difference in being the 9th prisoner to talk or the 11th, or the last: they will all hear what has been said before, and they can all see the colors of the hats of the prisoners ahead of them in the line. As we know that the 99 are saved, they all have the same information: the color the first prisoner said, and the colors of the 98 other prisoners' hat.

Particular case:

So let's first assume that there are only black and white hats. The prisoners agree that they will count 0 for black hats, and 1 for white hats. The first prisoner quickly counts the PARITY of the black hats, and says WHITE if it's even, BLACK if it's odd. Now all 99 prisoners can deduce the colors of their hat by counting the parity of black hats in front and behind them.

General case:

It gets a bit trickier with N colors, but the same idea leads to solution. The prisoners associate a number to each of the color. 0 for green, 1 for red, 2 for blue, etc. The first prisoner computes the sum of all the colors he sees, and the modulo of that number to N. He announces that number as a color. Now every prisoner can deduce the color of their hat, by computing the sum of the other prisoners' hat color and the modulo to N. Then if the number anounced by the first prisoner is 24 and I compute 22, I know that my color is blue, because adding 2 to 22 would give me 24, the number anounced by the first prisoner.

• The prisoners can all see each other? You should have made that clear in the question; that makes things much more solvable. From the way the prisoners are lined up, it sounds like they should see only the people ahead of them or only the people directly adjacent. – user2357112 Nov 16 '14 at 0:09
• It is not necessary for the prisoners to all see each other; notice that they can deduce the hat color of everyone behind them because everyone, except the first person guesses correctly, and they hear this - thus, when it comes to each person, they have enough information. So, if they can see everyone in front of them, they're golden. – Milo Brandt Nov 16 '14 at 5:00
• @Meelo: You're right, good catch. It's still not clear what the people can see, though. The answer says the prisoners can see the colors of the people "next to" rather than "ahead of" them, which seems to imply seeing both adjacent spots, and then it goes on to rely on people seeing far ahead. I think the "arbitrary range forward, no vision backward" version is more interesting than the "see everyone but self" interpretation, but whatever the case is, it really needs to be made clear in the question. – user2357112 Nov 16 '14 at 6:05
• @user2357112: I edited the answer to make it clearer! thanks – qdii Nov 16 '14 at 10:41
• Huh? There's no suggestion in the question that the executioner is going to alternate between hat colours. He could, say, use white hats three times in a row. – tobyink Nov 16 '14 at 11:22

Assuming the prisoners can see all those in front of them in the line but not those behind...

All the hats are the same colour, except that of the last in line. So the rearmost prisoner (say with a green hat) guesses the colour of all the others (say red) and is killed. The second prisoner sees the front 98 people are all wearing red, and knows the one behind him guessed red, so guesses he himself is wearing red. Ditto for all the others.

• Nope, this is a logical puzzle. The algorithm the prisoners use to solve it works for any combination of hats, not only a particular case. – qdii Nov 15 '14 at 19:14

Well, each prisoner just asked the others what color they hat was. Only the first prisoner had to guess, because the others hate him and didn't want to tell him his hat color.

Or

They just took their hat off, looked at it and then put it back. Only the first prisoner could not do that because he was disabled.

Well...