Solution to N hats in a row

How many can predict the color of the hat on their own head?

This is a problem which is extensively discussed online with videos and text. Here we present the general solution.

Here is the Problem: N people are lined up facing in the same direction. With their eyes closed, hats are placed on their heads. The hats are of two colors, either white or black. Each person can see the hats on the heads of people ahead of him. Starting from the last person in the line, they are asked to predict the color of the hat on their heads. What is the maximum number of correct answers possible if they use some rule?

If there are N people in the line, then the optimal algorithm can predict N – ½ correctly. The key idea is a concept called “Parity”. The idea goes as follows : the last person says white if he sees an odd number of white hats in front of him (parity odd or 1) and black (parity even or 0) if he sees an even number of white hats in front of him. Each person in line counts the white hats in front of him and adds to it the number of white hat calls from behind him, including the call from the last person. If this number is odd, he says W and if it even he says B.

Let us see how this works for one case with N = 7 with the sequence: LASTFIRST: BBWBWWB

We start with the last person who sees 3 white hats in front of him. Three is odd so its parity is 1. The last person calls W. The next person also sees 3 white hats in front of him and one W call from behind which add up to an even number, so he calls B.

Now the partial call sequence is WB.

The next person sees 2 white hats in front of him and there was one W call from behind which when added to the hats he sees is 3, an odd number, so he calls W, and we get the sequence: WBW

And in this way, it proceeds up the line. The key is to find the parity of the sum of the number of white hats you see in front of you plus number of white calls made so far, including the one from the last person. If this sum is odd call W else call B. The final call sequence is:

WBWBWWB.

Except for the wrong call from the last person in line, everyone else got their hat color right. Since the first person to make the call had a 50:50 chance that his hat would be the color he calls out, on average this algorithm gets N – ½ predictions right. To check if you understood see if you can work out the result for the sequence: WBBBWWBWBW. You should find that the called sequence is BBBBWWBWBW, which is correct except for the last person’s call.