Sunday 1 July 2012

Can Prisoners survive?


There were 100 prisoners which were asked to stand in a line such that the 100th one can see all, 99th one can see the other 98 and so on. There are two sets of cap Black and White. The king decides to put these caps on each of the prisoners(the prisoner can't see his cap but can see all people standing before him caps) randomly and then the king asked each of them to tell their cap color starting from the 100th prisoner, then 99th and so on. If the prisoner answers correctly, the king leaves him otherwise the prisoner is shot dead. If the prisoners are allowed to formulate a strategy, how many prisoners can be saved.
NOTE: Every prisoner can hear every priosoner's answer

2 comments:

  1. We can save 99 prisoners.
    100th prisoner can see 99 prisoners. Odd number of these has either black or white cap on. He calls out the color which is odd. The person at 99 can observe the number of people wearing black and white caps in front of him. If both are even, then the color of his cap is the 100th prisoners answer else it is the opposite. For 98th prisoner, if the answer of both previous two are same then the 99th saw even no. of hats for both else he saw odd number of hats for both. Hence he can know his color of hat.
    this process can be continued. Every one except the 100th prisoner can be saved.

    ReplyDelete