Riddle: Prisoners and Hats

  • #1
collinsmark
Homework Helper
Gold Member
2,919
1,319
I was listening to a rerun of "Car Talk" 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:

Answers and Replies

  • #2
6,265
1,280
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
20
7
Will the prisoners be free if most of them answers correctly or should all of them answer it right?
 
  • #4
collinsmark
Homework Helper
Gold Member
2,919
1,319
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
20
7
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
6,265
1,280
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
collinsmark
Homework Helper
Gold Member
2,919
1,319
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
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
26,149
9,537
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
collinsmark
Homework Helper
Gold Member
2,919
1,319
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
87
138
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
collinsmark
Homework Helper
Gold Member
2,919
1,319
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
Ibix
Science Advisor
Insights Author
2020 Award
7,306
6,385
I agree with V50. I am assuming perfectly reliable mental arithmetic under stress, which may be a tad unrealistic.
 
  • #13
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
26,149
9,537
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
Ibix
Science Advisor
Insights Author
2020 Award
7,306
6,385
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
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
26,149
9,537
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
259
786
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
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
26,149
9,537
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
259
786
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
collinsmark
Homework Helper
Gold Member
2,919
1,319
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
collinsmark
Homework Helper
Gold Member
2,919
1,319
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.]

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
259
786
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.
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
Ibix
Science Advisor
Insights Author
2020 Award
7,306
6,385
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
259
786
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.
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
Ibix
Science Advisor
Insights Author
2020 Award
7,306
6,385
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
collinsmark
Homework Helper
Gold Member
2,919
1,319
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.]

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:

Related Threads on Riddle: Prisoners and Hats

  • Last Post
Replies
9
Views
4K
  • Last Post
Replies
13
Views
1K
  • Last Post
Replies
2
Views
5K
  • Last Post
Replies
4
Views
7K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
3
Views
2K
  • Last Post
2
Replies
36
Views
7K
  • Last Post
Replies
15
Views
4K
  • Last Post
Replies
6
Views
3K
Top