Go back to previous page
Forum URL: http://www.cut-the-knot.org/cgi-bin/dcforum/forumctk.cgi
Forum Name: This and that
Topic ID: 641
Message ID: 0
#0, another question about prisonners
Posted by iliaden on Sep-29-05 at 10:02 PM
I found another problem about prisoners.

10 people are placed in a row, so that every one sees everyone who is in front of him (the second one sees only the first; the 10th sees everybody). A hat, either white or black, is placed randomly on the head of each prisoner, so nobody can see his own. In order, starting with the last one, each prisonner is given the chance to guess the color of his hat. If (s)he guesses correctly, (s)he is set free. If not, (s)he is killed. The goal is to save as many prisonners as possible.

I have a solution, that is quite simple:
The 10th prisonner names the color of the 9th prisoner's hat. He has 50% chance of survival, but the 9th has a 100% probability of survival. Then, the 8th prisonner names the hat of the 7th. Again, he has 50% chance of staying alive, but the next one has a 100% probability of survival. Follow the same pattern for the 6th and 5th prisonners; 4th and 3rd; and 2nd and 1st prisonners. Using this solution, 5 prisonners stay alive no matter what, and 5 others have 50% of chance of survival.

I believe that it is possible to keep the 9 first (or last) prisonners alive no matter what, and the 10th would have 50%, because he can't recieve any data from behind.

Please help!