Riddle: Prisoners and Hats

  • #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.
 
Last edited:
  • Like
Likes zoobyshoe and Vanadium 50

Suggested for: Riddle: Prisoners and Hats

  • Last Post
Replies
13
Views
2K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
4
Views
875
  • Last Post
Replies
14
Views
2K
MHB Riddles
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
31
Views
3K
  • Last Post
Replies
22
Views
6K
  • Last Post
Replies
2
Views
844
  • Last Post
Replies
16
Views
2K
Top