Friday, September 11, 2009

The Coloured Hats Problem

I've been enjoying Raymond Smullyan's "Satan, Cantor, and Infinity", trying to solve all the problems therein. This one is cute:

The Coloured Hats Problem

A student has placed a green hat on the head of each of three sleeping philosophers, X, Y, and Z. He wakes them up and explains that each of them is wearing a red hat or a green hat, but of course none can see what they themselves are wearing. The student first asks the philosophers to raise their hand if they can see at least one green hat. Of course, all three raise their hands. The student then tells them to put their hands down if they know the colour of their own hat. After a few seconds thought, the smartest philosopher puts her hand down. How did she solve the problem?

Solution

Let's assume the smart philosopher is X. X reasons that if X had a red hat then one of the other philosophers, Y say, would be able to immediately deduce that their hat must be green because Z raised his hand (Z sees at least one green hat). Since this has not happened, X concludes that her hat cannot be red and therefore must be green.