techInterview Discussion

A part of techInterview.org: answers to technical interview questions.

Your host: Michael Pryor

100 prisoners in a jail

I looked through the archives of techinterview.org and I was surprised that I didn't find my favorite puzzle. Sorry if I just missed it somehow, so here it is:

**
There are 100 prisoners in a jail. Since the jail will be closed, the prisoners are either released or executed. They are lined up in a single line in the backyard, and the guardians put a hat every prisoner's head, colored either black or white. The line is formed in a way that each prisoner can see the color of the hat of every prisoner in front of him, but none behind him, and no one can see their own hats. This way the first in line doesn't see any, the second sees the first, the third the first two, etc.

Now, starting with the last one in the line, every prisoner has to shout a color, black or white. If what he says matches his hat's color, he is released, otherwise he's shot in the head. All the other prisoners will hear what he shouted, and they will also hear weather he was shot or not. There's no communication between the prisoners, they have no knowledge of how many black/white hats there are in total, but they can agree on a strategy before the whole process starts.

What is the best strategy to save the most number of prisoners? How many prisoners can be saved for sure?
**
Laszlo Kozma Send private email
Monday, February 26, 2007
 
 
I have heard this before. Here is the strategy they all agree on:

The last person in the line has no information. So he can only hope that he is correct with a 50% chance. So he decides to help out his fellow prisoners. He says white if the number of caps white caps he sees on the heads of the other 99 prisoners is even, and black if it is odd.

Now the 99th person, knows whether to total number of caps is even, and he can see the other 98 caps. So he can deduce the color of had on his head, and would be let off.

The 98th person knows whether the total number of caps is even. He also knows the color of the cap on the 99th person's head. So he can compute the color of the cap on his head.

This way each person is able to correctly answer except the last person in line. There is a 50% chance that the last person will also be released.
Manu
Monday, February 26, 2007
 
 
say white = 1  and black = 0

the last one shouts
1) "white" if he sees odd white caps in front.
2) "black" if he sees even white caps in front.

the 2nd guy based on what 1st says and what he sees in front  will know his cap color
the 3rd guy based on what 1st,2nd guy say and what he sees in front can deduce his and so on...

with this we will have 99 people saved for sure.
whiz
Monday, February 26, 2007
 
 
now plzz excuse me for the repetetion... Manu posted while I was typing the solution :)
whiz
Monday, February 26, 2007
 
 
Please explain why the first prisoner cannot just shout the color of the cap of his fellow before him? This way 99th prisoner would know the color of his cap for sure without additional calculations. (100th prisoner would survive if his cap's color is the same as of 99th)
kobzarster Send private email
Tuesday, February 27, 2007
 
 
kobzarster: You are supposed to shout the color of the hat on your head, if you want to go free. So, if you shouted the color of the hat on the guy in front of you, you will get killed 50% of the time.
Manu
Tuesday, February 27, 2007
 
 
Congrats for Manu and whizz. 

If 100th shouts the one in front of him, then 99th can save his life. Then 98th has to save 97th and so on. With this strategy only 50 of the 100 would survive.
Laszlo Kozma
Tuesday, February 27, 2007
 
 
Laszlo: with this strategy we can expect 75 prisoners to survive.
Dmitri Papichev Send private email
Saturday, March 03, 2007
 
 
I was thinking of a generic solution to this problem .. as in what if the no of colours are more ?? Red, Blue Green ...

In that case we will have to use mathematics here...

In case of 3 hats we will have x exp 3 = 1 ... i.e x will be 1, w, w exp 2

And each colour can be equated as red =1 , Blue = w and green = w exp 2

And the nth person of the que shouts out the . of all the red , blue , green hats that he can see .. that helps guess the n-1th person to guess his colour of hat ..

so in case of 4 colours it will be -1,-i,i,1 ..

Thaughts ??
Maverick Send private email
Thursday, April 26, 2007
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz