An "Impossible?" Math Problem

As in, a problem from the math book "Impossible?" by Julian Havil:

There are a group of people in a room, and 15 people are given red hats and the rest are given blue hats. They can each see the color of everyone else's hats but can't see the color of their own hat. Also, they are all geniuses (and not the self-proclaimed kind, the real kind).  In other words, they all know logic perfectly (and they all know that they all know logic perfectly). A clock strikes every hour, and each person is told to leave when the clock strikes and they know they are wearing a red hat. In this situation, no one would leave, but if someone walked in and said, "At least one person is wearing a red hat," then everyone would leave after 15 strikes of the clock.  Sounds impossible, right?  (Explanation after the break)

Imagine if only one person was wearing a red hat.  When the person says, "At least one person is wearing a red hat," the one person with a red hat wouldn't see anyone else with one, and they'd know they're the one wearing it, so they'd leave after the first strike.  Everyone else with blue hats would see the one person with a red hat, and then they'd see that person leave.  Now if there were 2 people with red hats, if you're one of the people with a red hat, you'd still 1 other person with a red hat, so knowing that at least one person has one wouldn't be enough to know that you have one, so you wouldn't leave after the first strike.  But then, since the 1 person you see with a red hat wouldn't leave either, you know they must see someone with a red hat, or else it would be like in the first scenario and they'd have already left, and because you can see that everyone else has blue hats, it has to be you with the red hat.  If you can understand that, then you've got the basic idea.  If you see one person with a red hat and that person doesn't leave after the first strike, it's because you have a red hat on.  If you see two people with red hats and they don't leave after 2 strikes, you must have a red hat on... and so on until if you see 14 people with red hats and they don't leave after 14 strikes, you must have a red hat on, and so all of the 15 people with red hats would leave after the 15th strike.  Of course you can do it with any number you want, it doesn't have to be 15.


I thought it was an interesting problem.  I had never heard of a problem like it before I read the book "Impossible?".