- #36
collinsmark
Homework Helper
Gold Member
- 3,237
- 2,124
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.
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.
"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.
Last edited: