There are 100 prisoners. An executioner tells them that tomorrow morning, he will line them up so that each of them is facing the back of the head of another prisoner, except for one prisoner at the end of the line. In other words, prisoner 1 sees the back of the head of prisoner 2 as well as the backs of the heads of prisoners 3-100, prisoner 2 sees the back of the heads of prisoners 3-100, …, prisoner 99 only sees the back of the head of prisoner 100, and prisoner 100 doesn’t see any prisoners in front of him. The executioner tells them that he will put either a red or blue hat on each prisoner, then starting with prisoner 1 (the one who can see 99 other prisoners in front of him), will ask him what color hat he is wearing. The prisoner says a color and if he is wrong, he will silently kill that prisoner (prisoner 1 would be killed in a way that prisoners 2-100 won’t know if he was killed or not). If he is right, he will keep him alive. Then, the executioner will move to prisoner 2, ask the same question, and kill if he’s wrong, keep him alive if he is right. The executioner keeps doing this for every prisoner to prisoner 100. The prisoners are allowed to discuss together in the night what to do for the next day. What should their plan be in order to maximize the number of survivors? For clarity, what should their plan be in order maximize the number of survivors in the worst case scenario (any random guess by a prisoner ends up being wrong)?
Not the answer:
A sort of baseline answer is that prisoner 1 says the color of the hat worn by the prisoner right in front of him or her, thus sacrificing his or her life with a guess. Prisoner 2 is guaranteed to live. Repeat this for every pair of prisoners, giving us at least 50 prisoners alive at the end. With 2 colors of hats, it makes intuitive sense that this would be an answer. Unintuitively, this is far from the answer :-/
Answer:
One key, or hint, that may remain unemphasized when this brainteaser is presented to people, is that when a prisoner makes and says his guess for his own color, that guess is heard by all the other prisoners. If each guess is correct, that provides valuable information to the later prisoners.
Let’s say there are only 3 prisoners and we are the middle prisoner. We see only one prisoner in front of us and say he is wearing a red hat. From the perspective of the prisoner behind us, either 1 or 2 red hats are seen. So it’s possible for the prisoner behind us to announce through some code (e.g. “Red” = there is 1 red hat in front of me, “Blue” = there are 2 red hats in front of me) to tell us this. This allows us to answer our own hat correctly. Additionally, the prisoner in front of us will have gained two pieces of information: how many red hats there are with the 2 last prisoners and what hat the middle prisoner was wearing. In other words, initially, there were either 1 or 2 hats worn by the last two prisoners. The middle prisoner has the ability to answer correctly after the first prisoner sacrifices himself or herself by announcing the code. If the first prisoners announces that there are 2 red hats in front of him, the middle prisoner will definitely say that he himself is wearing a red hat, leaving 1 red hat for the last prisoner. If the first prisoner announces that there is 1 red hat in front of him, and then the middle prisoner says “Red,” the last prisoner knows that they are Blue, while if the middle prisoners says “Blue,” the last prisoner knows that they are Red.
Let’s say there are 4 prisoners in a line. The first prisoner sees 1, 2, or 3 red hats in front of him or her. But as long as the second prisoner announces his or her own hat color correctly, that will provide information for the later prisoners. So how can the first prisoner announce information so that at least just the second prisoner will get his or her own hat color correctly? The second prisoner sees 1 or 2 hats in front of him or her. The answer is that the first prisoner announces the oddness or evenness of the number of red hats he or she sees. From the second prisoner’s perspective, whatever he sees in front of him and whatever the last prisoner sees in front of him can only differ by 0 red hats or 1 red hat (whatever hat the second prisoner is wearing). Thus, the key is, when there is only a difference of one change at each increment, oddness and evenness conveys enough information to tell us what has changed. So the first prisoner sacrifices himself by announcing, say “Red” for an even number of red hats and “Blue” for an odd number of red hats that he sees in front of him. This allows the second person to say his hat color correctly. The third person has information that among the last 3 people, the number of red hats was either odd or even, plus what exact hat color the second person has, plus, of course, what exact hat color the first person, the person in front of him, has. Effectively, the second person knows the hat colors of all 3 people at the end of the line except his own color plus the information that the first person provides, what the oddness or evenness of the number of red hats was for those 3 people. This is enough information for the second person to figure out what color hat he has. It’s the same with the last person.
So with 100 people, the first person sacrifices himself by announcing the oddness or evenness of one of the colors that exist by code. The second person has exact knowledge of the colors of the 98 people in front of him plus the oddness or evenness of one of the colors for all 99 people excluding the first person (i.e. the 98 people in front of him plus himself), giving him correct knowledge of his own color. The third person know has exact knowledge of the color of the person behind him and the colors of the 97 people in front of him, plus the oddness or evenness of one of the colors for the 99 people that includes him, giving him enough information to figure out his own color. This continues until the whole line is finished. Thus, at least 99 out of 100 people can be saved with this strategy.
Extension:
What if the executioner uses more colors?
In our above case, we had 2 colors, and we sacrificed 1 prisoner at the beginning of the line to announce the oddness or evenness of one of the colors for the 99 people he sees in front of him. Since all prisoners know the number of prisoners that the first prisoner sees (99), everyone only needs to keep track of one of the colors, say red. The first prisoner announces the oddness or evenness of red, and each subsequent prisoner counts how many reds there are in the 99 to see if they also have a red hat or not.
If we have 3 colors, the first prisoner that can be saved would see x prisoners in front with 3 different colors and needs to figure out what color hat he has on. Extending the strategy from above, if we sacrifice two prisoners before him, they can announce the oddness or evenness of two of the colors. This is enough information for the first prisoner we save what color hat he has. All subsequent prisoners will then have exact knowledge of the hat colors of all prisoners that can be saved except for their own, which they deduce by the oddness or evenness of the 2 colors that that first two prisoner we sacrifice first announce. So in this case, we sacrifice 2 prisoners at the start and the 98 subsequent prisoners can be saved.
Let us apply the same logic to more colors. If the executioner uses y different colors where 1 ≤ y ≤ 100, the first y – 1 prisoners sacrifice themselves by announcing the oddness or evenness of y – 1 colors. The remaining 100 – (y – 1) prisoners will have enough information to correctly state their hat color. If the executioner uses more colors than there are prisoners, we don’t have enough prisoners we can sacrifice to convey accurate information about the oddness or evenness of the colors we have to prisoners at the end. In addition, we can always default back to the “baseline” solution, where each pair works together by sacrificing one prisoner (who simply announces the color of the hat in front of him) and saving the other one (who simply says the color that was announced by the prisoner before him), and guarantee at least 50 prisoners saved. Thus, for 1 ≤ y ≤ 49, the “sacrifice for odd or even” strategy saves 99 to 51 people. For y = 50, the strategy saves 50 people, which is the same as the result for the “default pair sacrifice” strategy. For y > 50 (and even if y > 100), the “default pair sacrifice” strategy can always save 50 people and becomes better than the “sacrifice for odd or even” strategy.