Question 116
The guard proposes the following game to the prisoners. All of them will be taken out into the yard, where each of them will have a hat of one of 5 possible colors put on his head. The guard will then line them up in a row so that every prisoner sees all the hats except his own, and ask the first prisoner in the row whether he knows the color of his hat. The prisoner answers aloud "yes" or "no". If he answers "no", he is immediately locked in solitary confinement. If he answers "yes", the guard will ask him what color his hat is, and the prisoner must answer in such a way that the other prisoners do not hear the answer. If the answer is wrong, that prisoner is immediately locked in solitary confinement in front of everyone, and if the answer is correct, that prisoner is immediately released in front of everyone. The guard then approaches the next prisoner in the row and repeats the same procedure, and so on up to the last prisoner. The prisoners may devise a strategy before the game begins, but once the game starts no communication among the prisoners is allowed. If there are 2015 prisoners in the prison, what is the maximum number of prisoners who are guaranteed to be released if the prisoners apply an optimal strategy?