11

# A Prisoner Problem

I went to a linguistics talk in college and learned a cool fact from sociology: across cultures and ages, human beings are interested in stories that have to do with

1. Death and danger
2. Power
3. Relations between the sexes

These three topics might be called the three universal areas of human interest. “It’s worth noting,” said the researchers, “that these are also classically ‘off-limits’ areas in school.” How funny, I thought.

Perhaps the interest in death, danger, and power is the reason we see various prisoner’s problems cropping up in mathematics. Here’s a fun one I just saw online, and which I thought about years ago… I don’t remember my previous solutions, though. I can definitely come up with a strategy to save at least 10, guaranteed, though I’m sure it’s possible to do much better.

Here’s the problem:

A warden tells 20 prisoners that they can live if they survive the following game: tomorrow the warden will line up the prisoners single file (at random), facing forward and place either a red or blue hat on each prisoner. Each prisoner can only see the color of hats infront of him. The warden starts from the back of the line and asks each prisoner in turn what color hat they think they are wearing. If a prisoner answers correctly they live, otherwise they die. No communication is allowed between prisoners once the game starts and they can only shout “red” or “blue” when it’s their turn. The prisoners have the evening to discuss a strategy. What is the best strategy for the prisoners? How many prisoners can be guaranteed to live?

1. Avery

This is one of my favorite puzzles. While it doesn’t fit your death/power/sex paradigm, I’ve always told this as you and 99 others win a contest. Same setup. For every hat that’s correct, \$1000 is added to the pot to be split evenly at the end (motivating collaboration). Anyway, I like this problem because there are opportunities for multiple aha moments and the best solution is, in my opinion, shocking (regardless of the number of prisoners, you can guarantee everyone but 1 person chooses correctly). Consider that a hint…

2. nate

We assume that the prisoners are able to hear the previous prisoners’ responses, but can we also assume that the forward prisoners learn whether or not each response was correct?

1. Post
Author
Dan

Ooo–good question. I always assumed you did hear whether their response is correct. The math teacher in me says: make both assumptions and see where each one takes you (but start with the easier one).

3. Debs

You don’t know how many there are of each color right?

I’m guessing the 10-guaranteed strategy is the following: The prisoners agree to an alternating pattern. Starting in the back with #20, the even numbered prisoners will say the color of the hat in front of them, and the odd numbered ones will say their own hat color (which they’ve just learned from the even numbered prisoner behind them). It’s a tough situation, because the odd numbered ones are guaranteed to be saved, if everyone plays nice, whereas the even numbered ones are gambling: only if their hat is the same color as that of the prisoner in front of them will they be saved.

It doesn’t have to be right in front of them; you could do the same thing with the guy in back saying the color of the guy in front, the guy second from the back saying the color from the guy second from the front, etc. The whole front half of the line, if they have good memories, will be saved.

And then the warden is sued for human rights abuses.

1. Post
Author
Dan

That was indeed my first thought. However, it turns out there is a much better solution. With the right strategy, it’s possible for 19 out of the 20 people to save themselves for sure.

4. Debs

Is it cheating to play with tone or duration? I was thinking it was less elegant to do so, but I was also thinking about how languages like Thai have different meanings depending on tone and duration. You could agree that long duration (“bluuue” or “reeeeddd”) means blue and short duration (“blue” or “red”) means red. Or that flat tone (like a statement in English) means red, but a rising tone (like a question in English) means blue.

This would allow you to say your own color, while tipping off the guy in front of you to his. Only the first person would be guessing, but even he’d tip off the guy in front of him.

1. Post
Author
Dan

There’s a sort of elegance to that, I’d say. But there’s also a solution that has nothing to do with how you say the word (just that everyone else hears it).

5. Debs

Hmm. If the prisoners have a good memory, they could do the following: after the first guy is eliminated, there will be 19 people left over. We don’t know how many hats there are, but out of 19, there’s got to be an even number of one color and an odd of another, right? Unless the warden is secretly into plaids? Since this is an odd situation to be in, the guy in back focuses on odds: he says “blue” if he sees an odd number of blues in front of him, and “red” if he sees an odd number of reds. Each subsequent guy has to pay attention to the color just said, so he can readjust the new odd/even balance of that color to guess his own hat.

It seems like a lot more to focus on under duress, though. ðŸ™‚

1. Post
Author
Dan

Excellently done! I love that this has such a good solution. It seems impossible, but it’s actually right there if you look at where the information is: the person behind you gives you information about what had they’re wearing; you know about everyone in front of you; so if the very first person gave you one more piece of information, it must be possible to deduce your own hat color.

(That may not be clear… it works better in my head)

Now… what if there were three colors instead of two?

1. Benny

Let n be the number of hats to choice from. Assign a point value to every hat, such that the first has a value of one, and the last (or Nth) has a value of n. Divide this summation by n, and view the remainder. It will be some number between 0 and n-1. Have the last person in line say a color that is code for the remainder he says. Then, have the person in front of him follow the same process, and, by seeing the change in remainder, he will be able to realize what color hat he has, as will each subsequent person. Or just cough a certain number of times before answering to hint at the next persons color…

6. Debs

Okay, I think I got it, after drawing out a bunch of options (admittedly as a slightly addictive form of procrastination). I got the basic premise quickly, but have been struggling to see if there was a solution that saved 19 people every single time. Instead, I found two possible solutions. Both save 19 people some of the time, and under some circumstances save 18 people for sure, with a pretty good chance for the 19th.

For either approach, everyone has to ignore the color of #20’s hat for this, and poor guy #20 has only a 1/3 chance for all his hard work. For the problem, all we care about are the 19 hats that #20 can see and thus share information about. Among these 19 hats, there are four potential patterns (let’s call the third color green)–
1. all are odd
2. red is odd and the others are even
3. blue is odd and the others are even
4. green is odd and the others are even
because since 19 is an odd number, we can’t have two odds and an even making it up (right?)

But the guy in the back has only three codes to use: red=red is odd, blue= blue is odd, green = green is odd.

If the truth is that all are odd, they have to come up with a different code system for that circumstance, and it will, under some circumstances, make it difficult to tell if #20 means that all are odd or one color is odd. I’ll call this system “the fallback person” — #20 can either name #19’s color or #18’s as a predetermined fallback if all colors are odd. I’ve been struggling with which is better, naming #18 or #19. I think choosing #18 is slightly better.

If only ONE color is odd, and #19 is the fallback person, then 19 people are saved. Let’s say it’s red, and it coincidentally belongs to #19. Then #19 quickly learns it must be his color, because he sees two even sets (blue and green) in front of him. But if his hat isn’t red, he knows this too: he sees odd red. He sees, maybe, odd blue and even green. But he knows they’re not all odd (red was stated and he sees odd red), and it isn’t a fallback situation. It can’t be two odds and an even, so his hat must not be green. His hat must be blue.

This would seem to mean it’s a good idea to pick #19 as the fallback person, right? But I’m not sure it is, because (I think) if ALL colors are odd, then while 19 knows his color, #18 then has a 1/2 chance of picking right (or per your Monty Hall puzzle, a 2/3 chance if he pre-picked one and switched?). We might be able to do better if #18 is the fallback for cases where all colors are odd. Everyone after 18 has enough info to determine the odds and evens and guess their own hats, but that’s true whether 18 or 19 is the fallback.

If instead of #19, #18 is the fallback, then the problems only arise, I think, when #18’s color matches the color stated by #20, because in that circumstance, it becomes difficult for #19 to determine for certain if all colors are odd or just the color named is odd.

If ALL are odd, #20 names #18’s color (let’s say it’s blue). Now, #19 has to figure out what to do. He knows his hat isn’t blue: blue is odd and he sees an odd number of blue hats. Let’s say he sees an even number of red hats and an odd number of green. It could be that blue is the only odd color and #19’s hat is green. But that’s the less likely choice, because we’ve introduced the other variable: it would have to be true both that blue is the only odd color AND that the pre-determined-if-all-odd guy, #18, happens to have a hat of that color. So, the more likely choice is that #19’s hat is red, since he sees an even number of reds, and in likelihood all colors are odd. He takes a pretty strong guess. And everyone ahead of him now has the information they need.

If #18 is the fallback and only ONE color is odd, then #19 and on can easily find the answer, unless the only odd color happens to match #18, in which case #19 has to make a pretty-good-chances guess again.

So, both 18 as a fallback and 19 as a fallback have drawbacks. It’s less likely to have all colors odd than to have one color odd, which on its own would favor choosing #19, but my guess is that when you also throw in the likelihood of #18 having the only-odd-color hat, and also the amount of hints the guesser (18 or 19) is working with in each situation, the solution would favor making #18 the fallback in cases of all odd colors.

Is this right so far? And is there an always-saves-19 answer I missed? Did I make this too complicated? It was fun to try.