Optimizing Prisoner Strategy for the Hat Riddle: A Simple Solution

[collinsmark]

I was listening to a rerun of "http://www.cartalk.com/" today on NPR and was reminded of this riddle. It's been on PF before, but not for several years (at least that I'm aware of). I thought I'd repeat it for those who haven't heard it yet.

I'm going to make a small modification to it though, and reword it slightly.

There's a penal colony on an island in the South Pacific. It's administered by a twisted prison warden who plays little mind games with the prisoners. He presents a challenge to the prisoners. If they solve it, they are set free. And if they don't, they're fed to the sharks.

The warden says to several prisoners (let's say the number of prisoners is at least 5, but less than 50), "I'm going to stand you against the wall. One guy is going to face the wall with his hands and his toes touching the wall. The next guy is going to stand behind him a few feet away, and the next person behind him and so on. Each guy can see the backs of the heads of the guys in front of himself, except for the last guy who can see everybody, and the front guy-- who can't see anybody.

"We're going to do this tomorrow," the warden says. "I want you to think about this overnight to see if you want to participate because, don't forget, if you lose -"

And if you win, you get set free. Here's how it works. The warden says, "Once everybody is lined up I'm going to place either a white hat or a black hat on each of your heads. I can put any hat I want on any of your heads. Once everybody is wearing a hat, I'll start at the back of the line working forward, where your job is to identify the color of your own hat correctly. There's one caveat. Nobody can communicate because only one guy at a time can speak [,and only when guessing the color of his own hat,] and the only thing he can say is either 'black' or 'white.' If there is any other communication whatsoever within the line, I'll feed you all to the sharks."

Crusty, who's been on this island for 19 years for overcharging for valve jobs says, "I have a plan which will improve our odds beyond 50/50. However, we must draw straws."

The question is what is Crusty's plan and why must straws be drawn?​

[Original, unmodified source: http://www.cartalk.com/content/prisoners-and-hats?question. Keep in mind my riddle is slightly different.]

Clarifications to avoid ambiguity:

• Although any given prisoner in line can only see prisoners in front of himself, he can hear all the other prisoners' guesses (either "black" or white"), even if he can't see them.
  
• The prisoners do not know how many hats will be black and how many will be white ahead of time.
• If it wasn't clear in the riddle, the prisoners are allowed to freely discuss their strategy and make a plan the night before.
• If you are unfamiliar with "drawing straws," it means somebody must be selected for a task that nobody volunteered for.
• Each prisoner will be freed if he answers right. Only those prisoners who incorrectly guess the color of their own respective hat will be fed to the sharks.
• Prisoners are not allowed to guess the color of their hat using an obvious high or low pitched voice, or answer in a funny accent, or anything that would change the normal timber and dialect of their natural voice. The only acceptable answer is either a simple "black" or "white." No funny business.

[Edit: here's an audio of the original broadcast that includes, more-or-less, the modifications that I made. In other words, my riddle here is pretty much exactly in line with the audio version of the riddle, except that the number of prisoners is not necessarily 5 in my riddle.
http://d2ozqge6bst39m.cloudfront.net/CT161208.mp3]

 

[zoobyshoe]

Crusty, who's been on this island for 19 years for overcharging for valve jobs...

I'm afraid this removes my motivation to save him from the sharks.

 

[Eucliddo]

Will the prisoners be free if most of them answers correctly or should all of them answer it right?

 

[collinsmark]

Will the prisoners be free if most of them answers correctly or should all of them answer it right?

Each prisoner will be freed if he answers right.

Only those prisoners who incorrectly guess the color of their own respective hat will be fed to the sharks.

(This of course assumes that they don't break the no-communication rule [where somebody says something other than "black" or "white," and only when asked to guess the color of his own hat], in which case they all die no matter what. We can assume that nobody breaks this rule.)

I've edited to the original post to add this clarification.

 

[Eucliddo]

Each prisoner will be freed if he answers right.

Only those prisoners who incorrectly guess the color of their own respective hat will be fed to the sharks.

(This of course assumes that they don't break the no-communication rule [where somebody says something other than guessing the color of his own hat], in which case they all die no matter what. We can assume that nobody breaks this rule.)

Ahh.. I see. Thanks!

 

[zoobyshoe]

The question is what is Crusty's plan and why must straws be drawn?

Spoiler

I'm thinking his plan would be for the back half of the line to use their guess to inform the front half of the line what color their hats are. The last guy at the back (who is the first to guess) would say the color of the first guy in line, absolutely informing him of what it is. The next guy, second from last, would say the color of the second from the front, and so on.

Straws must be drawn to see who is relegated to standing in the back half of the line. They only have a 50-50 chance of being right, and some will certainly end up shark food. All in the front half will be spared. Over all, the group has increased its chances to greater than 50-50, though.

 

[collinsmark]

Spoiler

I'm thinking his plan would be for the back half of the line to use their guess to inform the front half of the line what color their hats are. The last guy at the back (who is the first to guess) would say the color of the first guy in line, absolutely informing him of what it is. The next guy, second from last, would say the color of the second from the front, and so on.

Straws must be drawn to see who is relegated to standing in the back half of the line. They only have a 50-50 chance of being right, and some will certainly end up shark food. All in the front half will be spared. Over all, the group has increased its chances to greater than 50-50, though.

Not bad, but there's a better way.

Spoiler

Using your method, assuming a uniformly random distribution of hat color, it would increase the overall chances of survival to around 3/4 (each person in the front half of the line has a 100% chance of survival, and each person in the back half has a 50% chance of survival). Yes, it is better than 50/50 odds overall, at least. So that's good.

But there is a better way yet.

 

[Vanadium 50]

I think my solution is optimal: N-1 of them have a 100% survival rate, and one has a 50% survival rate.

 

[collinsmark]

I think my solution is optimal: N-1 of them have a 100% survival rate, and one has a 50% survival rate.

Spoiler

Yes, those are the optimal odds, I'm pretty sure. 'Sounds like you may have the correct solution.

 

[Pepper Mint]

I think my solution is optimal: N-1 of them have a 100% survival rate, and one has a 50% survival rate.

That is correct only in case all members agree to exhibit their altruistic behaviors.

 

[collinsmark]

That is correct only in case all members agree to exhibit their altruistic behaviors.

Yes, we can make that assumption.

Spoiler

It should be noted however, that in the correct solution, once everybody is already in line, it doesn't behoove anybody not to follow the strategy. Nobody would increase his survival chances by deviating from the plan.

So it's a fair assumption to say that everybody follows the plan once things are set in motion.

(Well, assuming the distribution of white/black hats is random.)

 

[Ibix]

I agree with V50. I am assuming perfectly reliable mental arithmetic under stress, which may be a tad unrealistic.

 

[Vanadium 50]

That is correct only in case all members agree to exhibit their altruistic behaviors.

What altruism? Nobody is worse off under this solution than in any other scheme.

 

[Ibix]

What altruism? Nobody is worse off under this solution than in any other scheme.

Everyone has equal odds until straws are drawn. Then one guy's odds are worse than everyone else's - and he is the lynch pin of the scheme. He has to accept that he's worse off than his mates and be big enough not to mess them up out of spite. That's altruism, I think. Everyone else has a strong selfish motive to follow the scheme, I agree.

 

[Vanadium 50]

Yes, but that guy's odds are not made any better. It's pure spite - and besides, this is not a psychology problem. And finally, he can't screw up everybody else. Just the next person. Once he is thrown to the sharks everybody ahead of him will know the color of their hat.

 

[Psinter]

Yes, but that guy's odds are not made any better. It's pure spite - and besides, this is not a psychology problem. And finally, he can't screw up everybody else. Just the next person. Once he is thrown to the sharks everybody ahead of him will know the color of their hat.

Are you sure of that?

I think you need communication. Stealthy communication. If you allow stealthy communication I think I can save all minus one, given that the stealthy communication is not uncovered. If it is uncovered all go to the sharks. So my method can save all minus one or send them all to the sharks.

Is communication okay as long as the warren doesn't notice?

Edit: I think your method also uses stealthy communication, Vanadium 50, since as you say, if the last one tries to screw the one in front, the rest will know the color of their respective hats.

 

[Vanadium 50]

I don't know what you mean by "stealthy communication". My method relies on a prearranged agreement about who says what, an agreement which saves, on average, N-1/2 prisoners.

 

[Psinter]

I don't know what you mean by "stealthy communication". My method relies on a prearranged agreement about who says what, an agreement which saves, on average, N-1/2 prisoners.

Oh. By stealthy communication I meant something that is so subtle that is barely detectable by the warren. With the con that if they get detected they all go to the sharks. My method doesn't have a prearranged agreement and that's why it requires the communication.

 

[collinsmark]

Oh. By stealthy communication I meant something that is so subtle that is barely detectable by the warren. With the con that if they get detected they all go to the sharks. My method doesn't have a prearranged agreement and that's why it requires the communication.

The only "communication" allowed is that each prisoner may speak a single word, either "black" or "white," and only once, when asked by the warden to guess the color of his hat. Nothing else is allowed, stealthy or otherwise.

 

[collinsmark]

I agree with V50. I am assuming perfectly reliable mental arithmetic under stress, which may be a tad unrealistic.

In the plan that I have (i.e., my solution), the "mental arithmetic" that each prisoner must perform, once in line, is kinda simple. It doesn't take a whole lot of brain power to follow the plan*. Each prisoner must pay attention to what's going on and maybe perform a quick mental comparison, sure, but there's nothing too taxing involved.

*(Coming up with the plan in the first place: well, that might be a different story. )

[Edit: if it helps, it is acceptable to assume that all prisoners are able to remain calm and alert, even under pressure.]

Everyone has equal odds until straws are drawn. Then one guy's odds are worse than everyone else's - and he is the lynch pin of the scheme. He has to accept that he's worse off than his mates and be big enough not to mess them up out of spite. That's altruism, I think. Everyone else has a strong selfish motive to follow the scheme, I agree.

It is acceptable to assume that nobody is overly spiteful. All prisoners are altruistic enough to follow the plan.

 

[Psinter]

The only "communication" allowed is that each prisoner may speak a single word, either "black" or "white," and only once, when asked by the warden to guess the color of his hat. Nothing else is allowed, stealthy or otherwise.

Even with a single word alone I was expecting them to deliver a message to the others in a chain such that at bad luck only 1 would have to be thrown to the sharks. My solution had only 3 possible outcomes which were:

• Only 1 go to the sharks (bad luck)
  
• All go to the sharks (worst case)
  
• All get saved (luck)

No casualties in between. But since my solution is not mathematical, but rather simplistic and primitive in thought, then I give up. My brain is not good enough to come with something mathematical.

In the plan that I have (i.e., my solution), the "mental arithmetic" that each prisoner must perform, once in line, is kinda simple. It doesn't take a whole lot of brain power to follow the plan*. Each prisoner must pay attention to what's going on and maybe perform a quick mental comparison, sure, but there's nothing too taxing involved.

Ah, but my solution takes no calculations whatsoever, just skills alone. I wasn't expecting this riddle to be mathematical. I give up, but I still think that if they have to pay attention then that's stealthy communication. Their calculations would be based on information they perceive of others be it directly or that it rebounds on the surroundings. Therefore the others are sending information. That is my logic.

 

[Ibix]

In the plan that I have (i.e., my solution), the "mental arithmetic" that each prisoner must perform, once in line, is kinda simple.

The mental arithmetic is about as trivial as you can get. It's just that the nth guy in line has to do n-1 operations, which is n-1 opportunities for error.

When do people get fed to the sharks? Immediately on error, or en masse at the end? In the former case you can recover from an error. In the latter I think pretty much everybody dies unless somebody else slips up and cancels the error.

 

[Psinter]

When do people get fed to the sharks? Immediately on error, or en masse at the end? In the former case you can recover from an error. In the latter I think pretty much everybody dies unless somebody else slips up and cancels the error.

On my case it doesn't matter when they are fed. The warren could have continued with the next without making a sound regarding the correctness or incorrectness of the answer. But I thought the same at one point while trying to come up with a plan.

The mental arithmetic is about as trivial as you can get. It's just that the nth guy in line has to do n-1 operations, which is n-1 opportunities for error.

Now I wonder what could be that so called calculation. Do you know it?

 

[Ibix]

The warren

Nitpick - you mean warden. A warren is a maze of tunnels where rabbits live.

Now I wonder what could be that so called calculation. Do you know it?

I have a solution that matches V50's description. I suspect we've got the same one and I suspect it's the best you can do.

 

[collinsmark]

Ah, but my solution takes no calculations whatsoever, just skills alone. I wasn't expecting this riddle to be mathematical. I give up, but I still think that if they have to pay attention then that's stealthy communication. Their calculations would be based on information they perceive of others be it directly or that it rebounds on the surroundings. Therefore the others are sending information. That is my logic.

Hmm. I think I might know what you're proposing. Something like saying "black" or "white" for your own hat, but saying it in a high-pitched or low-pitched voice as an indication of the hat color of the guy directly in front of you. I've never thought of that strategy.

I'm going to add an additional rule that that is not allowed. (This riddle is slightly mathematical, after all). Let's say that all the prisoners are horrible singers and they all have simple, monotone voices. They are all capable of clearly saying "black" or "white," but they are incapable of adding intonations or variety to their words. In addition, if the warden detects anybody using different pitches or different intonations in their guesses, he will throw everybody to the sharks. The only acceptable answer is a simple "black" or "white" with no varying pitches, no funny accents, or no anything that could carry additional information.

[Edit: I've updated the original post to reflect this new restriction.]

Now I wonder what could be that so called calculation. Do you know it?

Yes, the mathematical part is pretty simple, when it comes to actually following the plan. There are some bits of mental stuff each prisoner has to do and keep track of, but nothing too terribly difficult.

Creating the plan in the first place though is something some might find tricky.

 

[collinsmark]

When do people get fed to the sharks? Immediately on error, or en masse at the end? In the former case you can recover from an error. In the latter I think pretty much everybody dies unless somebody else slips up and cancels the error.

In my version of the solution it matters not when people get fed to the sharks.

If a given prisoner guesses his hat color incorrectly, he could be fed to the sharks immediately, or the warden could remain silent and wait until everybody is finished guessing, feeding all the wrong guessers to the sharks at the very end. Either way.

 

[Ibix]

In my version of the solution it matters not when people get fed to the sharks.

In my version it only matters if someone makes a mistake. Immediate sharking gives the information that someone messed up, which at least let's you restart the algorithm, and may even let you correct the error without further risk (I haven't quite worked that out).

If everyone performs correctly then it matters not.

Incidentally, at least in my scheme, if the warden works out my scheme he can rig the hats so one man is guaranteed to get eaten. It's only 50:50 if the warden is assigning hats on a coin toss.

 

[collinsmark]

In my version it only matters if someone makes a mistake. Immediate sharking gives the information that someone messed up, which at least let's you restart the algorithm, and may even let you correct the error without further risk (I haven't quite worked that out).

If everyone performs correctly then it matters not.

Yes, that sounds like my solution too.

It is acceptable to assume that once the plan is put in place, all of the prisoners will follow the plan verbatim with no mistakes (i.e., no deviations from the plan). They all are calm, collected and observant prisoners.

Incidentally, at least in my scheme, if the warden works out my scheme he can rig the hats so one man is guaranteed to get eaten. It's only 50:50 if the warden is assigning hats on a coin toss.

Correct (if the warden is aware of the plan's specifics).

We can assume that the warden is not aware of the specifics of the prisoners' plan. We can also assume that the prisoners don't know what particular scheme the warden is going to use when placing hats on anybody's head. Even if one of the prisoners seems to notice a pattern on the hats of those in front of him, he has no idea if that pattern continues to his own hat color.

 

[zoobyshoe]

I had to give up and google the solution. It's simple and beautiful and I never would have thought of it.

 

[collinsmark]

It's simple and beautiful and I never would have thought of it.

Yes. When I was listing to the Car Talk show yesterday, I had just finished a post (here on PF) involving the concept of a parity bit. And it all somehow seemed related to the Car Talk puzzler. There couldn't have been more than an hour between the two events. I found the coincidence too interesting to ignore.

So I felt compelled to post the riddle.

(there might be a hint in this post somewhere.)

 

[Vanadium 50]

parity bit

What we have here is a RAID - a Redundant Array of Incarcerated Desperadoes.

 

[Psinter]

Nitpick - you mean warden. A warren is a maze of tunnels where rabbits live.

Hahahaha. Thanks for the correction. I could have gotten it wrong in the future too and keep saying warren.

Hmm. I think I might know what you're proposing. Something like saying "black" or "white" for your own hat, but saying it in a high-pitched or low-pitched voice as an indication of the hat color of the guy directly in front of you. I've never thought of that strategy.

I'm going to add an additional rule that that is not allowed. (This riddle is slightly mathematical, after all). Let's say that all the prisoners are horrible singers and they all have simple, monotone voices. They are all capable of clearly saying "black" or "white," but they are incapable of adding intonations or variety to their words. In addition, if the warden detects anybody using different pitches or different intonations in their guesses, he will throw everybody to the sharks. The only acceptable answer is a simple "black" or "white" with no varying pitches, no funny accents, or no anything that could carry additional information.

[Edit: I've updated the original post to reflect this new restriction.]

Yes . Well, I'm officially out of order with that.

 

[collinsmark]

Anybody want to offer their solution (in spoiler tags of course)?

I'll post my solution in a day or two if nobody posts a working solution first.

 

[Vanadium 50]

Here's mine:

Spoiler

They line up so each prisoner can see the hats of all the prisoners ahead of them. The first prisoner doesn't know the color of his own hat, and says "black" if the number of white hats he sees is even, and "white" if it is odd. He has a 50-50 chance of making it. Prisoner 2 can see the number of white hats ahead of him, and knows if this is even or odd. If Prisoner 1 says "white" and he sees an odd number of white hats ahead, he knows his hat is black. A similar argument follows for the other three possibilities - in all cases, he knows the color of his hat. The same argument applies to Prisoners 3-N.

 

[Ibix]

V50 has the solution I had.