There is a party of logicians, and just towards the end of the party the host seats everyone down in a circle. They puts a hat on each person’s head such that everyone else could see it but the person themselves could not.
There were many, many different colours of hats. The host instructed them that a bell would be rung at regular intervals: at the moment when a person knew the colour of their own hat, they must leave at the next bell.
As they were all very good logicians, leaving at the wrong bell was unacceptable and would be disastrous to their reputations. The host reassures the group by stating that the puzzle would not be impossible for anybody present.
How did they all leave?
First we determine that there must be at least 2 of each hat colour. If there was a person with a unique hat colour, then they could in no way determine that their was even a valid colour. However, the host said that everyone has enough information to solve the puzzle and leave. Thus there must be at least two people with each hat colour.
We now form a hypothesis and prove it via induction:
Hypothesis: If there are
If there are only two people for a given colour
Suppose there are
Therefore, because the Hypothesis is true for
Therefore, everyone eventually leaves. (Compare this with Marked prisoners).