How Many of a Hundred Hatted Prisoners Can Save Themselves from the King?

November 28th, 2007 by Mark

Wayne sprung this question on me yesterday. I swear he should have been a CS major.

The Hundred Hatted Prisoners

There are a hundred prisoners in a dungeon, sentenced to be executed the next morning. Fortunately for them, the king of the land is eccentric and offers them a chance to survive. He tells them he’ll line them up, one in front of the other, with the most guilty in the back and the least guilty in the front. They’ll be bound, so it will be impossible for them to see those behind them, but they’ll be facing down a gentle slope and will be able to see all the prisoners in front of them clearly.

Next, the king will place a hat on the head of each prisoner. Some hats will be blue and some will be red, but the exact number of each is secret. The prisoner in the very back will be able to see which color of hats the other ninety-nine prisoners are wearing. The second prisoner will be able to see the hats of the ninety-eight prisoners in front, but not his own or the one on the prisoner in the back. It will continue like this, up to the prisoner at the very front of the line, who cannot see any of the hats.

Finally, the king will walk up the line, starting from the back, going to the front, asking each prisoner what color his own hat is. Anyone who answers incorrectly will be executed immediately, via silent odorless methods undetectable to those who haven’t yet been asked what color their hats are.

The prisoners may talk with each other tonight and collude to create a strategy for the next day. Once they are lined up for execution, though, they will not be allowed to speak, except to answer the king when he asks, “What color is your hat?” Even then, they may only utter a single word, “red” or “blue”.

If the prisoners work together with the right strategy, how many need to risk their lives?

This logic puzzle doesn’t really have a “sucker answer” like the coin-tossing one did, but the answer is a smaller number than one might first think. It’s a smaller one than I first thought.

Tags: friends, Geekery, math, puzzle, Wayne

This entry was posted on Wednesday, November 28th, 2007 at 3:59 am and is filed under Geekery. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

32 Responses to “How Many of a Hundred Hatted Prisoners Can Save Themselves from the King?”

1 Sonia Says:
November 28th, 2007 at 5:17 am
Muahaha, I actually know this one! Are you still offering drinks for the correct answer?

Maybe I shouldn’t say anything yet…but a friend of mine asked a bunch of us this question sometime last year, so it’s not really fair.
2 Michael Turton Says:
November 28th, 2007 at 9:32 pm
Unclear — they can say anything they please when the K asks, or just RED or BLUE?
3 Michael Turton Says:
November 28th, 2007 at 9:33 pm
Never mind my previous comment. LOL, it’s 0 or 1. Brilliant. Can you use the answer for JPEG compression routines?
4 Focks Says:
November 28th, 2007 at 10:47 pm
I was expecting a slightly different puzzle, but I’m intrigued to know the solution to this one.
5 Michael Says:
November 29th, 2007 at 12:05 am
Only one dies. Encode the even/odd-ness of one of the hat colors into the first speaker’s answer.
6 Michael Says:
November 29th, 2007 at 12:06 am
Well… only one “might” die
7 Ben Says:
November 29th, 2007 at 12:45 am
The only person who has to risk anything is the one at the back of the line - because he goes first and doesn’t know what colour he’s going to be. So he may as well say the colour of the person in front of him.

The person in front now knows the colour of his hat, and the person in front of him. They could devise some sort of code so that they say their own colour normally if it is the same as the person in front, and in an accent if it is different. Therefore everyone knows the colour of their own hat (except the first person) and can let the person in front know by using an accent.
8 Jason M Says:
November 29th, 2007 at 1:30 am
I say only 1 needs to risk his life, and that person is the one in the back. The riddle dictates that “they will not be allowed to speak” once in line, but does not dictate they are not allowed to communicate. So when prisoner 1 is asked what color his hat is, prisoner 2 could yank the chains (communicate) once for red or twice for blue. Only the last prisoner is at risk because no one but the king can see his hat color.
I guess you have to trust the prisoner behind you though, and hope that they aren’t a serial killer.
9 Kevin Says:
November 29th, 2007 at 1:44 am
Perhaps each person could just say whatever color is in front of him. Then, only the 1st person has to potentially “sacrifice” themselves (although they have no other option anyway from what I can tell). Everyone else just learns from the person behind them.
10 Kevin Says:
November 29th, 2007 at 1:50 am
Doht! Just realized my mistake … who’s to say that the person behind you will have the same color (ie, you can only choose one)! Should have thought about that one a little more.
11 Eric Says:
November 29th, 2007 at 2:16 am
binary is the key: before being paraded on the incline, they could agree to have the first prisoner (at the top of the incline) to potentially sacrifice his life for the greater good of the group (as he cannot see the color of his own hat and hence cannot with certainty save his life). Since he can however see the remaining odd number of hats (99), he could count the number of blues and if they add up to an even number, he could yell out blue, or red if they add up to an odd number odd. Armed with this information, the next prisoner counts the number of blue hats ahead of him and deduces the color of his hat based on whether there are an even number of blue hats left or not.

In short:
```
/**
  blue: an even number of blues
  red: an odd number of blues 
**/
if first guys shouts blue
  count blue hats in front of you 
  if the count is even
    shout red
  else 
    shout blue
else 
  count blue hats in front of you
  if the count is odd
    shout red
  else 
    shout blue
```
12 JD Says:
November 29th, 2007 at 2:34 am
I assume the back guy has to make a guess. But if he yells his hat color then the next guy would be BLUE, if he talks in a normal tone the it would be RED.

Or am I not thinking it through?
13 TH Says:
November 29th, 2007 at 2:58 am
it is easy if you think blue/red hats as 1/0 (binary).
14 Mark Says:
November 29th, 2007 at 3:32 am
Michael,

Back when I was in the video game programming business, we did some graphic encoding, and some was “lossy”, like JPEG. It involved Fourier transforms; this problem is just modular arithmetic. Maybe Wayne can fill us in on the background of this puzzle.
15 Keith Gabryelski Says:
November 29th, 2007 at 4:12 am
I’ve never heard this but I will take a guess

Only the first need sacrifice himself
he has a 50/50 chance of survival
all prisoners must trust everyone in back of them.
The rest are free

The collusion:

The first prisoner (to answer) guesses as to his hat color then answers the king in one of these ways:
a. red - if his hat is red and the same color as the prisoner in front of him
b. blue - if his hat is blue and the same color as the prisoner in front of him
c. not red - if his hat is blue and a different color as the prisoner in front of him
d. not blue - if his hat is red and a different color as the prisoner in front of him

all other prisoners know their hat color from the response from the prisoner immediately in back of them.
Their answer should encode the color of the prisoner in front of them as above.

Of course the front prisoner (last to answer) need not encode his answer.

If that is not acceptable, then, if all prisoners can hear all prisoners in back of them, 7 sacrifices are needed
from what I see.

all prisoners count the blue hats in front of them.
the first seven encode the number of hats in front of them in binary using blue for zero and red for one. The encoding is done front least significant bit to most significant bit.

All prisoners after 7 know the number of blue hats that are in front of them (and on their head) and can calculate if their hat is blue, subtracting one from the total number of blue hats as they hear prisoners behind them announce the blue hats on their head.
16 paning Says:
November 29th, 2007 at 4:13 am
Easy one.
Easy, one.
17 Jonathan Says:
November 29th, 2007 at 4:17 am
It is very simple. Only the last guy is at risk. Say 99 has a hat that is blue. 100 says “Blue,” and maybe dies, maybe not. 99 now knows his hat is blue. He looks at 98. If 98’s hat is blue, 99 says “blue” otherwise he says “it is blue.” The addition of the “it is” signals the man in front that the hat is the other color to that stated. This allows the current prisoner to state his own hat color, while informing the next prisoner of his hat color.
18 Mark Says:
November 29th, 2007 at 5:12 am
Jonathan and Keith,

The king summarily executes them all for conveying more information than “red” or “blue”.
19 Mark Says:
November 29th, 2007 at 5:15 am
Eric,

Bingo.
20 random Says:
November 29th, 2007 at 6:55 am
My solution:

The person at the back will have to guess.

If the person in front has red, answer quickly.
If the person in front has blue, wait before answering.
21 Jonathan Says:
November 29th, 2007 at 8:27 am
Algorithmically, Eric’s solution makes sense. Practically, it doesn’t. I’d hate to rely on everyone counting correctly - first mistake means everyone after that dies. Besides, I’m colorblind.
22 Quinten Says:
November 29th, 2007 at 2:48 pm
```
/**
  blue: an even number of blues
  red: an odd number of blues 
**/
if first guys shouts blue
  count blue hats in front of you 
  if the count is even
    shout red
  else 
    shout blue
else 
  count blue hats in front of you
  if the count is odd
    shout red
  else 
    shout blue
```
Eric’s solution doesn’t work. Testing with 8 prisoners:

from back to front:
r b r r b r b b
0 1 2 3 4 5 6 7
what happens:
0 shouts blue (4 blues ahead. he dies. oh well, he’s the most guilty.)
1 shouts blue (he is correct, and lives.)
2 shouts blue (first guy shouted blue and odd number of blues ahead. he dies.)
3 shouts blue (dies)
4 shouts red (dies)
5 shouts red (lives)
6 shouts blue (lives)
7 shouts red (first guy shouted blue and 0 is even. dies)

One has to consider the prisoners behind as well as the prisoners ahead. One can’t rely on the first prisoner’s choice and the prisoners ahead. This is obvious if you think about the front prisoner; he has no hats to count, so his answer can’t depend on the random choice of the back prisoner.

And remember, each prisoner can know what each prisoner before him has said. Here’s an algorithm that works:
```
blueBehind = number of prisoners behind you who have shouted blue
blueAhead = number of prisoners ahead who have blue hats

if blueBehind + blueAhead is even: shout blue
else: shout red
```
Using this algorithm:

from back to front:
r b r r b r b b
0 1 2 3 4 5 6 7
what happens:
0: 0 + 4 is even, shouts blue
1: 1 + 3 is even, shouts blue
2: 2 + 3 is odd, shouts red
3: 2 + 3 is odd, shouts red
4: 2 + 2 is even, shouts blue
5: 3 + 2 is odd, shouts red
6: 3 + 1 is even, shouts blue
7: 4 + 0 is even, shouts blue

Only 0 dies.
23 gtp Says:
November 29th, 2007 at 3:10 pm
Eric’s solution misses a step: The prisoners have to listen to the blue calls behind them and for each one swap the reference call from odd to even and visa versa.
24 TH Says:
November 29th, 2007 at 3:26 pm
Eric’s solution is basically calculating parity http://en.wikipedia.org/wiki/Parity_bit
25 Rajat Kala Says:
November 29th, 2007 at 3:41 pm
Dude, what are you guy talking about…. haha…
The real answer is: the maximum guys that has to die is 7 (taking the worst senario), the minimum is 0.

think……
26 Mark Says:
November 29th, 2007 at 7:30 pm
Yeah. I called that a bit quick. By realizing that he had to look at even vs. odd, he was 98% of the way there, but his solution didn’t quite make it.
27 Sriram Says:
November 30th, 2007 at 2:15 am
Have I misread the puzzle - it explicitly states that the number of hata of each colour is secret. Therefore the only known fact is that the sum of the counts of the red and blue hats is 100, or…?
28 Quinten Says:
November 30th, 2007 at 5:08 am
Sriram: the number of hats of each color is secret. But, every person knows the number of hats in front of him of each color. Each person also knows what each person behind him has said. It does not matter that the sum of the hats is 100.

If (the number of people behind who called blue) + (the number of people ahead who have blue hats) is even, then your hat is blue, otherwise it’s red. I am still having trouble explaining why this seems to work, but here are some more samples:
```
b b b b
0 1 2 3
0: 0 + 3: red
1: 0 + 2: blue
2: 1 + 1: blue
3: 2 + 0: blue

r r r r
0 1 2 3
0: 0 + 0: blue
1: 1 + 0: red
2: 1 + 0: red
3: 1 + 0: red

r r b b
0 1 2 3
0: 0 + 2: blue
1: 1 + 2: red
2: 1 + 1: blue
3: 2 + 0: blue

b b r r
0 1 2 3
0: 0 + 1: red
1: 0 + 0: blue
2: 1 + 0: red
3: 1 + 0: red
```
There are a couple patterns.
29 Matt Ball Says:
December 2nd, 2007 at 2:16 am
The most diabolical part of this puzzle is that the first prisoner can choose to kill everyone without changing his chances of survival. Each subsequent prisoner can only kill the remaining prisoners by killing himself.

There’s also an interesting moral dilemma if the first prisoner finds out the color of his hat accidentally, and determines that he must either kill himself so that the other 99 live, or he lives and the other 99 die…

Then there’s the practical problem of trusting each prisoner to do this kind of math correctly. If you performed this experiment with real people, at least a couple would mess up the calculation, causing strings of deaths until someone messes up again and corrects the sequence.

In practice, the safest thing is probably to have each odd prisoner state the hat color of the even-numbered prisoner directly in front, and each even-numbered prisoner state the previously stated color. In this way, 50 prisoners will assuredly live, and the other 50 would live half the time (expect 75 to live), and the complexity of the solution fits into even the simplest mind!
30 Xalem Says:
December 4th, 2007 at 1:43 pm
The strategy where every second player calls out the color of the hat in front of them is simple and 1/2 of the prisoners are safe. With a simple twist, 2/3 of the prisoners can be safe. (Only every third prisoner will risk death) The first prisoner calls out blue if the two hats in front of him match and red if the two hats in front of him differ. Then, when the first prisoner calls blue, the second prisoner calls the color of prisoner number three, and prisoner number three repeats that color. When number one calls red, prisoner 2 calls the opposite of prisoner 3, and prisoner 3 calls the opposite of prisoner 2. Then start over with the next set of three prisoners.

We can extend this to protect ever longer groups of prisoners. The first in any odd sized group (3,5,7,…) needs only determine whether the group (minus him) is composed of adding odd red hats and odd blue hats,or even red hats and even blue hats. Call blue for evens, red for odds. The rest add up what they see and what they hear and call red or blue based on whatever will make sure the result is parity (blue0 or not parity (red).

It would be possible to pick an arbitrarily large group (and only have one prisoner take a risk) but because people are human and all this calculating can lead to errors which would be catastrophic, I would tend to keep the groups small. But, now we have a strategy that matches whatever size of group feels they can handle the quick math.
31 Secruss Says:
May 13th, 2008 at 1:03 am
What Ben said.
32 Amit Hosley Says:
May 23rd, 2008 at 5:11 am
Answer is 99. The first can shout the color of Even Number of caps in front of him and then rest can calculate the correct colour of there ball. e.g. if the next person has even number of same colour in front of him then he has othe rcolour otherwise same. and rest can also make the calculations as they can hear all the answers.