Another hats puzzle

[wisnij]

Twenty prisoners are scheduled for execution, but the sadistic warden has decided they will play a game first. They are to be lined up facing in the same direction, such that each prisoner can only see those other prisoners in front of him. Each of them will be given a hat, which can either be red or blue, chosen randomly. Starting at the back of the line and moving forward, each prisoner will be given a chance to guess the color of his own hat. If he guesses right, he will be pardoned; wrong and he will be shot immediately.

The prisoners are given several minutes to talk with each other ahead of time. After the game starts and the hats are on, any attempt to signal each other or saying anything other than "red" or "blue" will result in them all being shot. What is the optimal strategy for them to follow, i.e. what will guarantee the greatest number of prisoners surviving?


I rather like this one because it's only moderately difficult for someone with a CS or mathematics background, but it's a real stumper for the average layman.

[xkcd]

I like this puzzle. I first heard it a couple months ago, and I remember sitting for quite a while going, "How about . . . no. Or maybe . . . no," until I finally got it.

[CactusEater]

only moderately difficult for someone with a CS or mathematics background, but it's a real stumper for the average layman.

im boned

[Enzo Dragon]

Sounds to me like the best thing to do would be to name off the hat color in front of you, starting from the guy in the back, until everyone but the guy in the back knows his own hat color for sure.

[xkcd]

Sounds to me like the best thing to do would be to name off the hat color in front of you, starting from the guy in the back, until everyone but the guy in the back knows his own hat color for sure.

No; the only chance you get to say a hat color is when you're asked what color your own is. If you say the color of the guy in front of you, he knows his hat color, but that leaves just a 50% chance that you've said the right color for you.

So yes, you could alternate, every odd-numbered person using his one chance to signal the guy in front of him his hat color, then that even numbered guy saying the color. There, you're guarenteed to save 50 people (more likely 75, but we're looking at worst-case).

But there's a much better solution.

[area]

Can I post what I think the solution is? I think I save all but one of the prisoners, but I don't want to spoil it for others...

[RealGrouchy]

ooh, I'd love to hear it.

It seems I'm only good at these things when I've heard them before.

[Penguin]

I'm pretty sure that I heard this on NPR's "Car Talk" a long time ago.

If I recall correctly, (not posting the entire solution so as not to spoil it), it has to do with odd/even numbers, yes?

[area]

I'm pretty sure that I heard this on NPR's "Car Talk" a long time ago.

If I recall correctly, (not posting the entire solution so as not to spoil it), it has to do with odd/even numbers, yes?

Yeah, that's the solution that I have.

[Sitnaltax]

I have a solution that saves 15 in the worst case. I can't see a better way to do it unless you have some underhanded way of conveying more information in the "red" or "blue" statement, which seems against the spirit of the question.

To determine if my solution is the same as yours: In my solution, if there were a 21st person, he would definitely be saved as well. If there are 38, then 32 would be saved.

EDIT: Never mind, the odd/even thing makes sense now.

[RealGrouchy]

It says that the colour of the hats is chosen randomly. Does that mean there are ten of each, or does it mean that there are 0-20 of each colour?

[xkcd]

0-20 of each color. Could be, say, all one or all the other.

[Penguin]

I don't want to be the irritating n00b who hops around to all the topics in a forum and spoils them for everyone, but I can post a/the solution to this problem if people don't mind.

[RealGrouchy]

I say don't (or at the very least, post it in a separate thread clearly marked "ANSWER" or similar), but if you don't mind could you pm it to me?

Cheers

- RG>

[sniffels]

They are to be lined up facing in the same direction, such that each prisoner can only see those other prisoners in front of him.

Does this mean that each prisoner can see every person in front of them and their hats? As in, the prisoner in the front of the line cannot see anybody and the second prisoner can see only the first, but the third prisoner can see the first and the second, and the fourth prisoner can see the first, second, and third, and so on?

If so, than I have a working solution. Good puzzle.

[area]

They are to be lined up facing in the same direction, such that each prisoner can only see those other prisoners in front of him.

Does this mean that each prisoner can see every person in front of them and their hats? As in, the prisoner in the front of the line cannot see anybody and the second prisoner can see only the first, but the third prisoner can see the first and the second, and the fourth prisoner can see the first, second, and third, and so on?

If so, than I have a working solution. Good puzzle.

That's the correct interpretation.

[Penguin]

I say don't (or at the very least, post it in a separate thread clearly marked "ANSWER" or similar), but if you don't mind could you pm it to me?

Sure, sorry for the delay with this. I'll try to get to it tonight...

[ZombieRoboNinja]

I've got it figured out for a 50% survival rate off the top of my head... is that the best possible?

EDIT: Nevermind, that solution was already mentioned.

[Vonkwink]

Sitnaltax: are you sure that you can definitely save 15 people? I have a solution that saves 13 in the worst case (16.5 expected value. meaning that one person gets partially killed. like a lobotomy or dismemberment or something) - but a slight miscalculation in this would make it seem like you could save 15. I'm wondering if my solution is the best one possible - I can't think of any way of improving it but maybe I am overlooking something.

[Oook]

As as been hinted at, there's a rather neat solution that is certain to save all but one of them.

[sniffels]

As as been hinted at, there's a rather neat solution that is certain to save all but one of them.

As in 19/20 of the prisoners? That'd be impressive. The best I have right now is 15/20.

[Penguin]

Yes, as in 19/20. That was, at least the last time I checked, twenty minus one.

The best solution has a 50% chance of saving all of them, too.

[Hawk]

Are they allowed to say "red" or "blue" more than once during their turn?

[wisnij]

The optimal solution is guaranteed to save 19 of them in the worst case, all 20 in the best case. There is a 50% chance of having the best case scenario. One more hint, though it might not help much: there is nothing special about the number 20. The optimal strategy is the same for an arbitratily large number of prisoners.

Are they allowed to say "red" or "blue" more than once during their turn?

No.

[Nicolas Bourbaki]

Here is my solution to the puzzle, which has nothing to do with even or odd numbers.

The last person in line (#N) says the color of the hat in front of them. #N-1 then knows his color. If it is the same as the color in front of him, he says that color at a normal speed. If it is different from the color in front of him, he says it ssslllloooowwwlllyyyy. In general, if person x+1 says their color normally, person x repeats the same color, either normally or slowly depending on if it matches the color in front of them. If person x+1 says their color slowly, person x says the opposite color, again either normally or slowly, depending on the color in front of them.

The warden will just think that about half of the prisoners are idiots!

[Spyike Johansson]

I've got a solution that also saves 19 or 20, but would be pretty obvious to the guard i guess...

[wisnij]

Here is my solution to the puzzle, which has nothing to do with even or odd numbers.

No special communication is allowed. (Maybe they make the prisoners write their answer, and then the guards announce what was written.) The solution does not rely on any tricks of voice, intonation, etc. It is purely a matter of what information each prisoner can determine from what was said by the others.

[sniffels]

I'm pretty sure that I heard this on NPR's "Car Talk" a long time ago.

If I recall correctly, (not posting the entire solution so as not to spoil it), it has to do with odd/even numbers, yes?

Yeah, that's the solution that I have.

Aight, I think I have the 19/20-person answer.

[Tropylium]

I thought a nice all-but-one-saved strategy might be for the last guy to say a code word that tells the colors of all the other guys' hats, before I noticed that saying sumthing else than "red" or "blue" will result in them all beïng shot. Damn. Anyone else fall for this?

Here is my solution to the puzzle, which has nothing to do with even or odd numbers.

No special communication is allowed. (Maybe they make the prisoners write their answer, and then the guards announce what was written.) The solution does not rely on any tricks of voice, intonation, etc. It is purely a matter of what information each prisoner can determine from what was said by the others.

I have a tweak for the solution abov: Can the prisoners remain silent for a period before answering? OK, this does end up beïng "communication", but they're not actually doïng anything…

…

No, wait; I think I got the non-comm answer, too.

<checks the solution>

…

Yeppers. Good puzzle.

[EndofEternity]

i think i got it, checking with the answer thread

[Mosterencedick9]

Spam in the place where I live (ham and pork)
Think about nutrition, wonder what's inside it now (oh boy)
Spam in my luchbox at work (it's the best)
Really makes a darn good sandwich any way you slice it at all

[Marlayna]

If it weren't for the spam, I would never have paid attention to this puzzle

I think I've found the solution. I feel soooo smart.

[jwwells]

A hint for the stumped:

Think parity. Think about encoding information about the number of blue hats in front of the first person. And think about how that changes with every correct answer.