Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Riddle: Prisoners and Hats

  1. Mar 20, 2016 #1

    collinsmark

    User Avatar
    Homework Helper
    Gold Member

    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: Mar 21, 2016
  2. jcsd
  3. Mar 20, 2016 #2
    I'm afraid this removes my motivation to save him from the sharks.
     
  4. Mar 20, 2016 #3
    Will the prisoners be free if most of them answers correctly or should all of them answer it right?
     
  5. Mar 20, 2016 #4

    collinsmark

    User Avatar
    Homework Helper
    Gold Member

    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.
     
  6. Mar 20, 2016 #5
    Ahh.. I see. Thanks!
     
  7. Mar 20, 2016 #6
    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.
     
  8. Mar 20, 2016 #7

    collinsmark

    User Avatar
    Homework Helper
    Gold Member

    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:
     
  9. Mar 20, 2016 #8

    Vanadium 50

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor

    I think my solution is optimal: N-1 of them have a 100% survival rate, and one has a 50% survival rate.
     
  10. Mar 20, 2016 #9

    collinsmark

    User Avatar
    Homework Helper
    Gold Member

    Yes, those are the optimal odds, I'm pretty sure. :biggrin: 'Sounds like you may have the correct solution.
     
  11. Mar 20, 2016 #10
    That is correct only in case all members agree to exhibit their altruistic behaviors. :DD
     
  12. Mar 20, 2016 #11

    collinsmark

    User Avatar
    Homework Helper
    Gold Member

    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.)
     
  13. Mar 21, 2016 #12

    Ibix

    User Avatar
    Science Advisor

    I agree with V50. I am assuming perfectly reliable mental arithmetic under stress, which may be a tad unrealistic.
     
  14. Mar 21, 2016 #13

    Vanadium 50

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor

    What altruism? Nobody is worse off under this solution than in any other scheme.
     
  15. Mar 21, 2016 #14

    Ibix

    User Avatar
    Science Advisor

    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.
     
  16. Mar 21, 2016 #15

    Vanadium 50

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor

    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.
     
  17. Mar 21, 2016 #16
    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.
     
  18. Mar 21, 2016 #17

    Vanadium 50

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor

    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.
     
  19. Mar 21, 2016 #18
    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.
     
  20. Mar 21, 2016 #19

    collinsmark

    User Avatar
    Homework Helper
    Gold Member

    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.
     
  21. Mar 21, 2016 #20

    collinsmark

    User Avatar
    Homework Helper
    Gold Member

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

    It is acceptable to assume that nobody is overly spiteful. All prisoners are altruistic enough to follow the plan.
     
    Last edited: Mar 21, 2016
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Riddle: Prisoners and Hats
  1. A Riddle (Replies: 6)

  2. Prisoner Hats (Replies: 9)

  3. Hat Riddle (Replies: 4)

  4. A riddle (Replies: 23)

Loading...