Optimizing Prisoner Strategy for the Hat Riddle: A Simple Solution

[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.

 

[collinsmark]

Here is my solution. It's equivalent to @Vanadium 50's solution, but I'll go into more detail with emphasis on it being simple -- mentally speaking -- in terms of what each prisoner must do while in line.

Spoiler

So, Crusty explains that each prisoner must be observant and keep track of two things, the "running parity" and their own special "personal parity."

"The first thing you need to figure out," he says, "is to determine whether the number of white hats in front of you is even or odd. Use whatever method you want; count them, pair them up, whatever. But you do need to figure this out before the guessing gets started. You can do this in conjunction with the warden putting hats on people, so there's really no rush -- you'll have plenty of time. Call this evenness or oddness your 'personal parity.' It is either even or odd. Your personal parity is even if there are an even number of white hats in front of you. Your personal parity is odd if you see an odd number of white hats. You only need to figure this out once and it never changes. By the way, zero counts as even, so if there are zero white hats in front of you, your personal parity is even.

"Next, you'll also have to pay attention to something we'll call the 'running parity.' The running parity starts out even. Every time you hear somebody behind you guess 'white,' the running parity toggles. It starts out as even. The first time somebody says 'white,' the running parity changes to odd. The next time somebody says 'white' it changes back to even. And so on.

"When somebody guesses 'black' the running parity remains what it is. If it was even it stays even. If it was odd it stays odd. Only 'white' guesses make it change from even to odd or odd to even.

"So here is what you do when it's your turn: Compare the running parity to your personal parity. If they are the same, you have a black hat, so say 'black.' If they are different you have a white hat, so say 'white.'"​

The way I worded it above is equivalent to the first guy -- the guy in the back of the line -- saying "white" if the number of hats he sees is odd, and "black" if he sees an even number of white hats (same as @Vanadium 50's solution). I phrased it the way I did so the guy in back doesn't need to follow any special rules. But it's equivalent: he has a 50/50 chance of making it out alive. All the other prisoners have 100% chance of being set free if they follow the plan.