The Prisoners' Hats, Part 2

Frustrated that Albert, Barry, and Carl had solved his first hat puzzle so easily, the warden concocted another.  This challenge still involved black and white hats, but an unknown number of each hat and 100 prisoners.

He brought 100 prisoners from their cells and told them he would line them up in single file, all facing the same direction, such that each could only see those in front of him.  A hat would be placed on each prisoner's head such that he could not see its color.  There could be any number from 0 to 100 black hats and 0 to 100 white hats involved.  Then starting with the prisoner at the back of the line, each prisoner would say either "Black" or "White". If every prisoner correctly identified the color of his own hat, they would all go free.  But if any prisoner was wrong, they would all be executed.

One prisoner complained, "But there's no way we can guarantee that we all correctly guess our own hats!  Our best chance is 50-50!"

At this, the warden, feeling generous, said he would grant the prisoners one error.  "One prisoner is allowed to be wrong - with the right strategy, you should all be able to guess your own hat color with absolute certainty."

They have an hour to plan a strategy.  What should they do?

Solution:

This is difficult to describe with text alone, but bear with me.  Let us identify the prisoners by their order in line.  The prisoner in the front of the line will be #1, the next one behind him will be #2, and so on.  The last prisoner in line, #100, is going to be called on first.  He can see everyone in front of him, but there is no way for him to accurately guess the color of his own hat.  Rather than actually try to guess the color of his own hat, he will speak in code.  He will count the number of white hats in the line in front of him.  If the number of white hats in front of him is odd, he will say "Black."  If the number of white hats in front of him is even, he will say, "White."  Now the next person in line, #99, will count the number of white hats in front of him.  If he sees the same number of hats as #100, he will know that he is not wearing a white hat, because he and #100 are looking at the same set of hats.  If he sees one fewer hat than #100, then he knows that #100 is looking at his (#99's) own hat in addition to the hats that #99 sees; in this case, he is wearing a white hat.  Continuing down the line, each prisoner will keep three pieces of information to identify his own color:

• Number of white hats ahead
• Number of white hats that have been called behind (not counting #100's call)
• Whether the total count is odd or even, according to #100's original call

Clear as mud?  Let's consider an example.

Say the warden places 55 white hats and 45 black hats on the prisoners.  #100 doesn't know what color hat he is wearing, but he sees 55 white hats in front of him.  Since this number is odd, he will say, "Black".  It doesn't matter whether he's right or not, because they are allowed one mistake.  #99 only sees 54 white hats in front of him.  He knew that #100 either saw the same 54 hats that he was seeing, in which case he would be wearing a black hat, or that #100 saw 55 hats - the same 54 hats he was seeing, plus an additional white hat on his own head.   Since #100 said "Black", #99 knows that it is an odd number: 55.  This must mean that he is wearing a white hat on his own head, and says "White".

Let's move on to #98.  #98 sees 54 hats in front of him.  He also now knows that #99 is wearing a white hat, because #99 just said so.  That brings the count of white hats that he's aware of to 55.  But he has to think about what #100 sees.  If he (#98) is wearing a white hat, then #100 sees all 55 that he is aware of plus his (#98's) own white hat = 56 total.  If he is not wearing white hat, then #100 sees only the 54 white hats in front of #98 plus the white hat that #99 is wearing = 55 total.  Since #100 said "Black", #98 knows that it is an odd number: 55.  This must mean that he is wearing a black hat, so he says "Black".

This logic continues all the way to the front of the line.  Each prisoner will keep a running count of the white hats he sees in front of him and the white hats he hears behind him (not counting #100's hat).  Keeping in mind whether the total number of white hats is odd or even, he will be able to deduce the color of his own hat.  As long as everyone can keep track of this in their heads, they will be fine.