Q. There are 100 prisoners standing in a row, all facing forward in one direction, i.e., the 100th prisoner can see the 99 prisoners in front of him, the 99th can see 98 in front of him, but can't see the persons standing behind him. All the prisoners are wearing a hat, of either Red or Black color. But, they don't know the color of their hat. They are asked one by one the color of hat they are wearing, starting from the 100th prisoner. If they give correct answer, they will be spared, else executed. They are not allowed to talk to other prisoners, but before the execution process, they were allowed to discuss some strategy, so that maximal number of people could be saved. Find out the maximum number of persons that can be saved.
Solution: 99
Let the prisoners be standing in a row as shown below, facing in the same direction.
=> => => => .... .. . . . . .. . . . .. . => =>
100 99 98 97 2 1
So, the strategy they can devise is that, 100th person when asked the color of his hat will count the number of Red and Black hat in front of him. And say, if the number of Red hat is even, then shout Red else shout Black. So, the if the 99th person sees that the number of Red hats in front of him is still even, then he is wearing a Black hat else Red.
Similarly all the persons from 99 to 1 can correctly guess the color of their hat.
So, 99 persons can be saved. The 100th person has 50-50 chance.
No comments :
Post a Comment