So here’s a puzzle I read a short time ago. I came up with a solution that kinda worked, but then read a far better answer for it. Let’s see what you come up with.

There are 20 prisoners on death row, all set to be killed tomorrow. The executioner sets up this challenge:

“Tomorrow, all 20 prisoners will stand in a row. Each prisoner will be able to see only the prisoners standing in front of him/her. So the last prisoner will see all 19 in front, while the front prisoner will see no one. Each prisoner will then be given a hat, either WHITE or BLACK, placed on their head. You will not be able to see the color of your own hat, only those of the people in front of you. You will not be allowed to communicate in any way with anyone while standing in line, nor will you be able to turn or look at anyone but those in front of you. Violation of any of these rules will result in instant death for everyone.”

“Once this is all set, starting with the last prisoner in line, I will ask ‘What color is your hat?’ You can answer only ‘BLACK’ or ‘WHITE’, anything else means instant death for everyone. If you guess right, you live. If you guess wrong, you die. We move to the next person in line (the 19th) and ask the same question. This continues through all the prisoners.”

The prisoners are free to communicate through the night. Can you come up with a way to guarantee the life of some prisoners? How many?

No, I can’t.

The first one to answer (last one in line) is pretty much screwed. He has a fifty/fifty shot.

The volume of the voice should indicate what the person directly in front of you has. If you say your guess loudly, then the person in front of you has on a black hat. If you say your guess quietly, then the person in front of you has on a white hat.

This should save 19.5 out of 20 prisoners (.5 being that the first guy has a 50-50 shot at it).

Rob has essentially come up with the same solution that I did. I think it works, but can be made to not work with a slight rules change. There’s also the potential for error. Still counts as good.

Also Rob’s now a dad! Everyone congratulate Rob and weep for our future.

If they know the number of hats of each color everyone can count and they’ll all be OK. But you didn’t say that they do.

So how about this:

They can only answer “black” or “white”, but they could agree on a signaling system based on volume. The first person to go (i.e. the 20th person in line) says the color of the next person’s hat. He has a 50% chance of living. The next person says the color of his own hat, which he’s just learned from the person behind him, but if the next person in front has the same color hat he says it very loudly while if the next person has the other color he says it very quietly. The next person now knows what color his hat is and they can continue down the line that way. So at most one person is in trouble.

Klaas came up with the exact same answer as I did. It works based on the rules presented, but it seems likely that the executioner would figure out what was going on, and change the rules slightly and make it not work. Technically, changing the rules is against the rules, but he’s an

executioner, why would he care?The best I can do is slightly better than half. Each prisoner could announce the color of the hat in front of him or her. This would save at least 50% and probably 75% because each person would know there color and have a 50% chance of getting right their own color.

If I’m the 20th person, I say the color of the hat in front of me. The 19th person then says that color. The 18th person then says the color of the hat in front of him, so the 17th person lives, etc. At least 50% will live, and the even number people have a 50% chance. So, 10 – 20 could be saved

Or, the 20th person state the color of the most hats and everyone says that color, thereby saving above 50% of the people. at least 10 people would be save.

This may not the “correct” answer, but it could work.

If you say your answer in a high, squeeky voice, that means the person in front of you is wearing a white hat, but if you say it in a low baritone voice, that means they are wearing a black hat. That way, only the last in line would have a potential of dying.

Since the prisoners can communicate the night before they agree to use some voice prompts to let the person in front of them know the color of their hat.

For example, if the person in front has a black hat, they would say the color of their hat (which would be a 50/50 guess for the last person in line) loudly. The loudness would indicate to the person in front that their hat is black.

The could use volume or other voice tricks (e.g. weeping voice) as they say ‘white’ or ‘black’ to let the person in front know what their hat color is.

Only one person will die, the last one in line. Each prisoner says the color of the hat of the person standing in front of him/her

The first answer is the one that Klaas, Rob, etc. came up with: The first (i.e. back of the line) guy has a 50/50 shot of living, and everyone else ought to live. Just say the color loudly if it’s the same as the person in front of you, and quietly if it’s not. So the back guy guesses, and the next guy knows (based on the previous guy’s volume), yada yada. And at the least, all but 1 prisoner survives.

The only issue with that solution is if for some reason you don’t actually get to hear the previous guy say his answer. E.g. if the executioner makes you write it down, and he reads the answer instead, or you have to whisper it in his ear, and he repeats it. Then you’re screwed and you die.

The other solution I read, which is rather clever, is this: The first person (the guy in the back, who can see everyone) still has a 50/50 shot no matter what. What he does is says “WHITE” if there is an even number of white hats in front of him, and “BLACK” if there is an odd number of white hats in front of him. Since he’s got a 50/50 shot anyway, his chances don’t change at all. The next guy knows if there’s an even or odd number of White hats, and can see everyone in front of him, so he’ll be able to tell if the number of white hats in front of him is STILL even/odd, or if it has CHANGED. If it has changed, he must say WHITE. If it has not, he says BLACK. The next person, knowing that the original person said even/odd, and hearing the person before him say White/Black will know if there’s currently an Even or Odd number of white hats, can look forward, and then make the same choice.

Essentially, each prisoner must start with what the first person said: Let’s say he said White, meaning there was an even number of White hats. Now every prisoner is currently thinking “Even”. The next person goes, counts the number of white hats. If there is an odd number, he knows he has a white hat as well (since the total must be even) so he says “White”. Now any time anyone says “White” all the remaining prisoners change what they were remembering (currently it was “Even”) to the opposite (So now “Odd”). The next person goes, and the process continues. Every time anyone says “White” the remaining prisoners switch what they’re remembering. Thus the last person will say “White” if when it gets to him he’s remembering “Odd” and “Black” if he’s remembering “Even”.

Rather clever.