Another Weekend Puzzle

A hundred people are held captive in a prison by a small-scale dictator. They are all very intelligent, and while away their days creating and solving logic puzzles. Each one is assured of all the others’ strong logical abilities.

One morning, the warden tells the hundred prisoners that the dictator wants to close down the prison, so each prisoner must either be executed or released. Since there are no records on why any of the prisoners are there, the warden has decided to make his decisions on the basis of a game. At 7am the next morning, all the prisoners will be lined up in front of the wall in the courtyard and blindfolded. Then, three guards will walk behind the row of prisoners, putting one hat on each. Some hats will be red, some will be yellow, and some will be blue, in whatever proportions the guards decide to use. Once all the hats have been put on the prisoners, the first prisoner will have his blindfold removed and will be led slowly down past the other prisoners. Then, after he has seen everyone else’s hat, he will be asked the colour of his own hat. If he answers correctly, he will be released. If he doesn’t, he will be shot. Either way, his hat will be placed on the ground on the spot where he stood, so that the other prisoners can see it. The same thing will then happen to the second prisoner, then the third, and so on down the line, with every prisoner in turn having his blindfold removed, being able to see each other prisoner or the hat he left behind, and then having to guess his colour: a correct answer securing release, an incorrect one leading to death.

The warden makes clear that each prisoner will be permitted to hear each other prisoner’s guess, but that this is the only information that can be conveyed from one prisoner to another. If any other attempt is tried to get across information — if any prisoner modulates his voice, or scuffs his feet, or does anything else to transmit any message to another prisoner — then the game will end and all the prisoners will be executed.

For the rest of that day and through the night, the prisoners puzzle over what they should do. At worst, each of them has a 1/3 chance of being released: he merely has to guess at random. But they can do better than that, since there is a way for them to transmit information to one another while doing nothing more than making their guess. For instance, if there were only two prisoners, the first could see what colour the second prisoner’s hat is. Suppose it were red. Then, the first prisoner could guess “Red”, and the second prisoner (having already prearranged this system with the first) would then be guaranteed his release, since he would be bound to get the answer right. The first prisoner, meanwhile, would be stuck with a 1/3 guess, since he would only survive if his hat happened to be red as well.

So, there are ways of guaranteeing the release of some of the prisoners. The question is, how many prisoners’ releases can be guaranteed using the best method? 33? 50? 75? More? And, of course, what is the best method?

20 thoughts on “Another Weekend Puzzle

  1. The prisoners could have an arrangement by which they will all say whatever the first prisoner says. If the first guy says “red,” everyone who comes after him will say “red.” They will never vary their response.

    The problem states: “Some hats will be red, some will be yellow, and some will be blue, in whatever proportions the guards decide to use.” So, it’s possible that the majority of hats are a single color. If the first prisoner stands up and sees a sea of red hats, with only a couple yellows and blues thrown in there, he should say “red.” That gives him the best odds of survival as well as communicating what everyone else should say to promote their own survival, too.

    If the first prisoner sees 90% red hats, he’s just boosted the survival rate from 33% to 90%. But if the proportions of the three colors are evenly split, this strategy works no better than chance.

    Like

  2. Thanks for getting this started, Stonedead!

    You’re right that in some cases, this strategy will boost everyone’s chances; but if the colours are roughly evenly distributed, it will only help out a minority (who will already have a 33% chance anyway).

    This seems to be a tough one! I’ll move things along a little by providing a step toward the answer.

    Here’s a strategy that _guarantees_ that each even-numbered prisoner will definitely survive: the odd-numbered prisoners always guess whatever colour is worn by the person directly ahead of them in line. For instance, if Prisoner #37 sees that Prisoner #38 is wearing a yellow hat, (s)he guesses yellow. If the prisoners all agree to this strategy in advance, then Prisoner #38 will know for sure to guess yellow. As for the odd-numbered prisoners, they have a 1/3 chance of happening to guess their own hat colour correctly by doing this.

    So, that _guarantees_ safety to 50 prisoners (the even-numbered ones), and leaves the other 50 with a 1/3 chance.

    But it’s possible to guarantee the safety of _more_ than 50 prisoners, if you adopt the right strategy! How many more? And what’s the strategy?

    Happy solving!

    Like

  3. I have not got the answer. The strategy you laid out is that half the prisoners are supposed to sacrifice their own interests and speak solely to communicate lifesaving information to a designated partner. Once it’s framed like this, it’s hard to imagine how the success rate could increase. Each man is only allowed to speak one word. The word has to be spoken twice (thus by two men) to save someone’s life: first to be passed on from the saver to the savee, second to be used by the savee. It does seem inefficient, but I can’t think of an alternative right now…

    For purely dramatic purposes — if we were screenwriting — I wouldn’t make the odd-numbered prisoners the savers and the even-numbered prisoners the savees. The pattern would become apparent because the guards would hear “red,” “red,” “yellow,” “yellow,” “blue,” “blue,” and based on this echo, they’d figure out that the prisoners were communicating and that overall two-thirds were surviving when only one-third should. Instead, I would have the first 50 prisoners designated as the savers and the last 50 as the savees. Two-thirds of the first 50 drop dead. The last 50 sail through without a scratch. It’s harder to figure out how they learned the answers, because the information was communicated several dozen gunshots ago. But that doesn’t raise the survival rate.

    To communicate more complex information to multiple people, I think the saver has to be able to give an apparently false answer that can be decoded.

    How about:
    Prisoner 1 agrees that:
    – If he sees the same color hat on both Prisoner 2 and 3, he’ll say the name of that color.
    – If he sees different colors on Prisoner 2 and 3, he’ll say the name of the color that ISN’T represented.
    So, if Prisoner 1 says “red,” and Prisoner 2 and 3 can see that each other’s hats are red, they know that their own hats are red, too.
    If Prisoner 1 says “red,” and Prisoner 2 can see that Prisoner 3’s hat is blue, and Prisoner 3 can see that Prisoner 2’s hat is yellow, both 2 and 3 know their own hat colors. It’s the color that is neither seen nor heard.
    I think this guarantees survival for 66 of the prisoners and the remaining 34 (including the last guy who’s not part of a triad partnership) take their chances.

    Like

  4. Superb, stonedead! It took me a day or so longer than you to figure out that part. You’re right: with the technique you developed 2/3 of the prisoners (66 of them) can have their safety guaranteed, with the rest having a 1/3 chance of surviving.

    But… it’s possible to do even better than that, ingenious though your method is!

    How much better? Well, this might surprise you. Of the hundred people, the first _must_ be stuck with a 1/3 chance of survival, since absolutely nobody else can communicate anything to him/her. The question is, how many of the remaining 99 can have their safety guaranteed?

    Amazingly, the answer is: _all_ of them!

    To put it another way: after surveying the other 99 people, the first prisoner to be asked to speak is able, by naming one of the three colours, to communicate enough information to _all_ the other prisoners that _each_ one will have enough information to work out with certainty his or own colour. Your answer is on the right track!

    Like

  5. An interesting puzzle with a long history! The form puzzles take is always interesting: Given: some set of facts, an original conditions statement, and some rather important conditions that will produce a conclusion. But when I look at puzzles like 100 prisoners and n hats I’m almost immediately drawn from the world of logic and math to the world where we live.

    Here are some real puzzles: What are the odds of getting 100 people who can think clearly and imaginatively under the stress of death? What are the odds that once an axiom is developed to save 99 that all will remember how to proceed? What are the odds that someone won’t faint or drop dead before morning? The world we live in, happily for us, is much more chaotic than the logician’s world.

    Like

        • One of my favourite memories of puzzles: On the way to class one morning I stopped at a dollar store and bought the hats for the puzzle you link to and took them to class where I went thru the steps with volunteer students. Almost immediately the first student who could see no hats shouted out the correct answer. Wow! thought I. Tell us how.
          “I can see my reflection in the window.”
          Good old empiricism.

          Like

        • I agree that it was clever of the student to be on the lookout for other ways of solving the problem (just as it would be clever for someone playing poker to take advantage of the fact that she could see another player’s hole cards in the window reflection in deciding whether and how much to bet).

          But in logic as in poker, if those opportunities don’t present themselves, you’d better have some general skills.

          Like

    • Bob, I had a similar objection when I was first introduced to the trolley problem in college. I had a hard time seeing it as a true ethical dilemma since, in the time it takes to say, “My, this seems to be an ethical dilemma,” the trolley has already crashed and the problem is moot. Its all-round implausibility was (and still is) very distracting for me.

      Regarding the hat puzzle, maybe it becomes less distracting and stressful if the story is different. No mass executions. Instead, it’s students whose A, B, and C grades are posted to a noticeboard. By some mechanism, they can see everyone’s grades except for their own (the TA makes them come by one at a time to see the noticeboard and hides the relevant one; or, it’s online, and the computer hides it). They are asked to publicly guess their own grade, and if they guess correctly, they’re excused from writing the final paper. Or, it could be workers who are guessing at their managers’ evaluations because they are promised a bonus if they guess correctly.

      …I still can’t figure out the answer.

      Like

      • Another person who feels bothered by hypotheticals! I’ll write a response, but… tomorrow.

        For now, here’s the solution! You were actually getting close, stonedead.

        The prisoners are taken outside and lined up in some order. The hats are placed on their heads. The first one has his blindfold removed, and is led down the line. He sees each hat. In advance, the prisoners agree to give a numerical value to each colour to each hat: for instance, yellow could be 2 (easy to remember because ‘yellow’ has two syllables), red could be 1, and blue could be 0 (since zero degrees centigrade is freezing). Prisoner #1 keeps a running total as he goes, adding 1 to the total for every red hat and 2 for every yellow hat. At the end, he divides the total number by 3, and calls out the colour that corresponds to the remainder. (For instance: if he counts 64, then he divides that by 3 (giving him 21 remainder 1) and then he calls out red (for 1, which was the remainder). If he counts 81, then he divides that by 3 (giving him 27 with no remainder) and then he calls out blue (for 0, which was the remainder). That colour also serves as his guess, which he has a 1/3 chance of getting right. Sadly, he couldn’t improve on that.

        However, all the other prisoners can now figure out their colours with certainty, since they can inspect all 98 of the other hats that the first prisoner saw and do the sum themselves. The only difference is that their own hat is not counted. For instance, suppose that the first prisoner counts 64 hats. As we saw, this leads the first prisoner to guess red, since there is one remainder left over when you divide 64 by 3. Now suppose you are one of the other prisoners: it doesn’t matter which one. You add up the totals of the hats of the other prisoners (leaving aside prisoner #1, whose hat was not involved in the first prisoner’s calculation) and get the remainder. Let’s say you see 63. Then you have a remainder of 0. But the prisoner’s guess — red — is 1. Therefore, your hat must have whatever value would, when added to 0 (the number you see) bring the total to 1 (the number the first prisoner saw). The only number that, when added to 0, gets 1 is 1 (red). Therefore, your hat is red. Or, suppose you see 64. Then, like the first prisoner, you would normally call out red. but this is exactly what the first prisoner did call out! So the difference between what you see and what the prisoner saw must be 0. Therefore, your hat has a value of 0: it’s blue.

        In general:
        – If the number you would call out is exactly the same as what the first prisoner called out, your hat is blue.
        – If the number you would call out is one less or two greater than what the first prisoner called out, your hat is red.
        – If the number you would call out is one greater or two less than what the first prisoner called out, your hat is yellow.

        Like

        • I never would have guessed it. My mind is not even of the caliber to see how my 66-man approach is related to the 99-man approach! Except in the general sense that there is an answer to be decoded. But I didn’t think of assigning numeric values to the colors.

          Like

      • True, stonedead, you might not have the time to figure out the best course of action in the trolley case in the seconds you’d have to decide what to do (just as someone playing a sport might not be able to painstakingly calculate the right decision in the middle of a game). But I don’t see why that’s a problem for the question.

        The trolley problem is meant to put some abstract principles to the test. But even beyond that:
        – If you ever faced a relevantly similar situation, your having thought through your general stance on these sorts of issues would be helpful.
        – If someone else faced an issue, you would have all the time you needed to sort out whether he or she had done the right thing.

        The problem does not lose its force or importance merely because you would not have time to sort out the answer at the moment. And nobody I know of who has written on the trolley problem ever suggested or assumed anything that would imply that.

        Like

    • Oh, Bob: I’m starting to think that sob1989’s aversions might stem in part from your influence! I had no idea.

      I’m curious:
      – Does this aversion of yours apply to other puzzles and games as well? Do you resist playing hangman until it’s made clear to you what the accused is being hanged for and the exact details of his crime? Do you avoid playing checkers because it makes no sense for the same nation to have two or more kings simultaneously?
      – Do you find yourself unable to make any moral assessment of Biblical stories (e.g. the famous one of Abraham and Isaac) because the supernatural details make the story obviously counterfactual?
      – When faced with mathematical problems involving a car travelling a certain distance at a certain rate, do you find yourself unable to make progress on sorting out how long it took until you’ve been told who the driver was, the reason for the trip, where the drive took place, what the weather was like, how it was possible for the rate to be perfectly constant when there was surely traffic somewhere, and so on?

      If not, then your qualms about this logic problem seem arbitrary!

      Like

  6. We publish stories that have been forwarded to us by prisoners in Wisconsin, so that the general public can read what is really being done with their tax money. We also publish stories from the media about Wisconsin prisons. Showing that Human Rights are not at all common in the USA. Especially when you are incarcerated, more so when you belong to a minority.

    Like

  7. Pingback: Looking Back | Episyllogism

Please join the discussion!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s