Optimizing Prisoner Strategy for the Hat Riddle: A Simple Solution

  • Thread starter collinsmark
  • Start date
  • Tags
    Riddle
In summary, the prisoners are given a task (to guess the color of their own hat) the night before and only those who guess correctly are set free.
  • #1
collinsmark
Homework Helper
Gold Member
3,382
2,612
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]
 
Last edited:
Physics news on Phys.org
  • #2
collinsmark said:
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.
 
  • Like
Likes collinsmark
  • #3
Will the prisoners be free if most of them answers correctly or should all of them answer it right?
 
  • #4
Eucliddo said:
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.
 
  • #5
collinsmark said:
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!
 
  • #6
collinsmark said:
The question is what is Crusty's plan and why must straws be drawn?
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.
 
  • #7
zoobyshoe said:
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. :biggrin:

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. :woot:
 
  • #8
I think my solution is optimal: N-1 of them have a 100% survival rate, and one has a 50% survival rate.
 
  • Like
Likes Pepper Mint
  • #9
Vanadium 50 said:
I think my solution is optimal: N-1 of them have a 100% survival rate, and one has a 50% survival rate.
Yes, those are the optimal odds, I'm pretty sure. :biggrin: 'Sounds like you may have the correct solution.
 
  • #10
Vanadium 50 said:
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. :DD
 
  • #11
Pepper Mint said:
That is correct only in case all members agree to exhibit their altruistic behaviors. :DD
Yes, we can make that assumption.
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.)
 
  • Like
Likes Pepper Mint
  • #12
I agree with V50. I am assuming perfectly reliable mental arithmetic under stress, which may be a tad unrealistic.
 
  • #13
Pepper Mint said:
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.
 
  • #14
Vanadium 50 said:
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.
 
  • Like
Likes Jeff Rosenbury
  • #15
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.
 
  • #16
Vanadium 50 said:
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.
 
  • #17
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.
 
  • #18
Vanadium 50 said:
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.
 
  • #19
Psinter said:
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.
 
  • #20
Ibix said:
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. o0))

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

Ibix said:
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.
 
Last edited:
  • #21
collinsmark said:
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.
collinsmark said:
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.
 
  • #22
collinsmark said:
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.
 
  • #23
Ibix said:
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.
Ibix said:
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?
 
  • #24
Psinter said:
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.
 
  • #25
Psinter said:
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.]

Psinter said:
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.
 
Last edited:
  • #26
Ibix said:
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.
 
  • #27
collinsmark said:
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.
 
  • #28
Ibix said:
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.
 
Last edited:
  • #29
I had to give up and google the solution. It's simple and beautiful and I never would have thought of it.
 
  • #30
zoobyshoe said:
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.)
 
  • #31
collinsmark said:
parity bit

What we have here is a RAID - a Redundant Array of Incarcerated Desperadoes.
 
  • Like
Likes Jeff Rosenbury, Enigman, collinsmark and 1 other person
  • #32
Ibix said:
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.
collinsmark said:
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 :biggrin:. Well, I'm officially out of order with that.
 
  • #33
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.
 
  • #34
Here's mine:

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.
 
  • Like
Likes Ibix and collinsmark
  • #35
V50 has the solution I had.
 
  • Like
Likes collinsmark
<h2>1. What is the Hat Riddle and why is it important to optimize prisoner strategy?</h2><p>The Hat Riddle is a classic logic puzzle that involves prisoners wearing either a black or white hat and trying to guess the color of their own hat without being able to communicate with each other. It is important to optimize prisoner strategy because it can potentially lead to a successful escape and highlights the importance of strategic thinking and cooperation.</p><h2>2. What is the simple solution to optimizing prisoner strategy for the Hat Riddle?</h2><p>The simple solution involves the first prisoner counting the number of black hats and then guessing the color of their own hat based on whether the number is even or odd. The remaining prisoners then use this information to determine the color of their own hat. This strategy has a 50% chance of success.</p><h2>3. Are there any other strategies that can be used to optimize prisoner strategy for the Hat Riddle?</h2><p>Yes, there are other more complex strategies that can be used, such as using a predetermined code or signaling system. However, the simple solution is the most efficient and has the highest chance of success.</p><h2>4. How does the number of prisoners affect the success rate of the simple solution?</h2><p>The success rate of the simple solution remains at 50% regardless of the number of prisoners. However, the more prisoners there are, the more difficult it becomes to execute the strategy effectively without any errors.</p><h2>5. Can the simple solution be applied to other similar logic puzzles?</h2><p>Yes, the simple solution can be applied to other similar logic puzzles that involve a group of individuals trying to determine a specific piece of information without being able to communicate with each other. It highlights the importance of teamwork and strategic thinking in problem-solving scenarios.</p>

1. What is the Hat Riddle and why is it important to optimize prisoner strategy?

The Hat Riddle is a classic logic puzzle that involves prisoners wearing either a black or white hat and trying to guess the color of their own hat without being able to communicate with each other. It is important to optimize prisoner strategy because it can potentially lead to a successful escape and highlights the importance of strategic thinking and cooperation.

2. What is the simple solution to optimizing prisoner strategy for the Hat Riddle?

The simple solution involves the first prisoner counting the number of black hats and then guessing the color of their own hat based on whether the number is even or odd. The remaining prisoners then use this information to determine the color of their own hat. This strategy has a 50% chance of success.

3. Are there any other strategies that can be used to optimize prisoner strategy for the Hat Riddle?

Yes, there are other more complex strategies that can be used, such as using a predetermined code or signaling system. However, the simple solution is the most efficient and has the highest chance of success.

4. How does the number of prisoners affect the success rate of the simple solution?

The success rate of the simple solution remains at 50% regardless of the number of prisoners. However, the more prisoners there are, the more difficult it becomes to execute the strategy effectively without any errors.

5. Can the simple solution be applied to other similar logic puzzles?

Yes, the simple solution can be applied to other similar logic puzzles that involve a group of individuals trying to determine a specific piece of information without being able to communicate with each other. It highlights the importance of teamwork and strategic thinking in problem-solving scenarios.

Similar threads

  • General Discussion
Replies
2
Views
5K
Replies
10
Views
3K
  • General Discussion
Replies
25
Views
3K
  • General Discussion
Replies
6
Views
14K
  • General Discussion
Replies
14
Views
6K
  • General Math
Replies
8
Views
4K
Replies
9
Views
5K
  • General Discussion
Replies
2
Views
3K
Replies
15
Views
4K
  • Math Proof Training and Practice
3
Replies
83
Views
17K
Back
Top