Riddle: Prisoners and Hats

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

 

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