There are 64 prisoners who are to be executed the same day. The executioner didn't want to waste his whole day getting the electric chair set up and preferred to shoot them all. However, he thought it would be unfair to deviate from the procedure and just shoot them without giving them a second chance. So he thought of a plan.
He informed all the 64 prisoners that they would be made to stand in a line in such a way that each of the prisoners could view the heads of all the prisoners standing in front of him, and then the executioner would put one hat on each prisoner's head which would be either white or black in colour (The prisoners would not be able to see the colour of the hat on top of their own heads). Then each of the prisoners would be given a chance to shout out the colour of his own hat starting from the last prisoner (The prisoner who can see all the hats except his own). Whoever shouts out the wrong colour would be shot and the others let go.
The prisoners have quite a good unity and they want most of them to be saved. You have to help them device a strategy which if they follow would make the probability of saving all the prisoners highest!
5 comments:
The worst case is (0.5)^64
When collaborating, the worst case becomes (0.5)^32 in which every alternate prisoner shouts the color of the person standing infront of him. The color might match his own hat's color as well - so probability become 1/2 for each...
worst case .. the first (last prisoner) guy who calls will die ... else all will be safe .... odd/even trick
Last guy sees 63 hats
63 = n Whites + (63-n) Blacks
Count of either one of Black and White hats has to be even.
The last guy shouts the color the count of which is even. The probability of him dying is 1/2
The next guy sees 62 hats and he knows the hat color which is even, including his own hat color
So, he can determine his hat color.
So on and so forth.
The final probability of everyone remaining alive is 1/2 :)
@skp, @Vivek: Good work!
ingenious!
I was going for (0.5)^ceil(n/3), where n = 64 here: the last prisoner rescues the two chaps ahead of him, by shouting Black if they both sport hats of the same color, else White. So, for every triplet, the probability of all surviving is 1/2.
Post a Comment