An island holds 100 blue eyed and 100 brown eyed people, all perfect logicians. Nobody may discuss eye colour and nobody can see their own. Anyone who deduces his own colour leaves that midnight. A visitor announces publicly that at least one person has blue eyes. What happens, and on which night?

An island holds 100 blue eyed and 100 brown eyed people, all perfect logicians. Nobody may discuss eye colour and nobody can see their own. Anyone who deduces his own colour leaves that midnight. A visitor announces publicly that at least one person has blue eyes. What happens, and on which night?

Approach: Solve the cases of one and two blue eyed people first, then induct, and ask what the announcement adds when everyone can already see a blue eyed person.

All 100 blue eyed people leave together on the 100th midnight. Induct on the number k of blue eyed islanders. When k is 1 that person sees no blue eyes, so the announcement identifies him and he leaves on night one. When k is 2 each of them sees exactly one blue eyed person and expects him to leave on night one, and when nobody does, each deduces his own colour and both leave on night two. The same step gives night k for general k. When k is at least 2 the announcement tells nobody anything he did not already see. What it creates is common knowledge, the unbounded chain of everyone knowing that everyone knows it, and the induction consumes exactly one level of that chain per night. The brown eyed people never learn their own colour.

Follow-up: If the visitor instead says that at least two people have blue eyes, on which night do the 100 leave?

Key concepts: common knowledge, induction on the count, public announcement.