End Of The Line

So, its time for the solution to the Hats in a line problem. I've always like this problem, because when I first learned it I got lucky and managed to solve it in under an hour. Its not uncommon though to take a few days.

Anyway, the solution is easy enough:

Treat the hat colours as 0 or 1, the person at the back states the value you get by taking the XOR of the front 99 hats. The next person from the back can see the front 98 hats and knows the parity, so that is enough for them to be correct. The next person can see the front 97 hats and knows that the person second from the back was correct, and knows the parity of the first 99 hats, so that is enough information for them. It is easy to see that each person will be correct now except possibly the one at the back, who is 50/50 to survive.

Its not hard to see this is optimal, as the person at the back cannot possibly do better than 50/50 with zero information, and everybody else is 100%. Its also interesting to note that having on "idiot" in line will not kill everybody in front of them. They will be wrong, and they will screw up the person in front of them, but after that the two mistakes will cancel out. This is even true if the person at the back of the line is incorrect for some reason.