Hats In A Line

Alright, time for a new puzzle. I haven't put much thought into what puzzle I wanted to post next, so I guess I'll just go with one I have known for ages. Possible that most of my readership has already seen this also (all two of you), but I'm also just posting it for my own archiving purposes.

Anyway, I first learned this one from Bart:
There are 100 people in a line wearing hats. Each hat is either white or black, and each person can see all the hats in front of them, not their own hat or any hat behind them. Then, some disreputable men in black suits will come and ask each man a simple question: "What colour hat are you wearing?". They begin asking at the back and move forward in the line one person at a time. The people can only answer with "white" or "black". For each person, if that person is correct they are silently released, if that person is incorrect they are silently killed. Every person in front of them can hear their answer.

The people may get together and plan before the hats are assigned. What strategy guarantees the maximum number of people survive?

I would like to call the rule about seeing all the hats in front of you and none behind you "standard line hat rules", but theres only one other problem I know of that even uses that rule, and it involves the axiom of choice.

No comments: