Mathematical Induction

A group of men, all versed in logic, sits around a table. Fifteen of them are wearing red hats, the rest blue. Each can see the others' hats but not his own. On the table is a clock which strikes once each hour. The men are given the following instructions: 'You are not allowed to discuss the color of your hats. However, should any of you find that he is wearing a red hat, he should leave the table on the clock-strike immediately following his discovery.' Now it is assumed that no one is initially aware of the color of his own hat. Furthermore, since the men cannot see the color of their own hats, nor discuss it with their colleagues, nothing happens for a while. Then a guest arrives. She looks at the hats around the table, and says, clearly: 'At least one man here is wearing a red hat!' What happened and why?

"An induction argument can be used to show that once the guest has made her announcement all individuals with red hats will eventually leave the table. This contradicts one's feeling that nothing should continue to happen; after all, apparently the guest has not provided any new information."

--Mathematical Fallacies, Flaws, and Flimflam

After I thought and thought about this for way too long, the answer just popped into my head and it was so freaking simple I was annoyed at myself. Induction is kind of cool.