Terrence Tao quotes an (apparently) widely known problem, briefly paraphrased:

There is an island upon which 1000 people with various eye colors live. 900 have brown eyes, and 100 have blue. Each resident can (and does) see the eye colors of all other residents, but is forbidden by custom to try to discover one’s own (no talking about it, etc.). If (and only if) one does discover one’s own eye color somehow, then one commits suicide the following day for all to witness.

One day a visitor unaware of island customs comes to the island and announces (truthfully) to everyone: I see at least one blue-eyed person among you. What happens next?

One might be tempted to say that nothing happens, since every islander already sees either 99 or 100 blue-eyed people, so the visitor seemingly brought no new information.

But this is not true. In fact, every islander eventually commits suicide. We can show this by mathematical induction on the number of blue-eyed persons K that a particular islander can see.

First note that the only relevant information in this problem are the visitor’s statement and the visible actions of other islanders. Furthermore, committing suicide on some day k is equivalent to discovering one’s eye color on exactly day k-1.

Proposition 1 (base case): Seeing 0 blue-eyed persons is equivalent to discovering one’s own eye color to be blue on day 0 (i.e. the moment) of the visitor’s statement, and committing suicide on day 1.

Proof: The only situation in which I can discover information on day 0 is if I see 0 blue-eyed persons, making the visitor’s truthful statement a contradiction if I were not blue-eyed. (The information obtained is exactly my own eye color.) ∎

Proposition 2: Seeing 1 blue-eyed person is equivalent to discovering one’s own eye color on day 1, and committing suicide on day 2.

Proof: The only situation in which I can discover information on day 1 (but not before) is if the visitor’s statement is uninformative, but the action of those discovering information on day 0 is informative. The latter information, by Proposition 1, is whether there is exactly 1 blue-eyed person (if he commits suicide on day 1) or not (if he does not). Therefore, I must be deciding whether there are 1 or 2 blue-eyed persons, i.e. I see 1 blue-eyed person. (The information obtained is again my own eye color.) ∎

From these we can figure out what the induction step needs to be:

Proposition 3 (induction step): If it is true for all k from 0 to K that seeing k blue-eyed persons is equivalent to discovering one’s own eye color on day k and committing suicide on day k+1, then it is also true that seeing K+1 blue-eyed persons is equivalent to discovering one’s own eye color on day K+1 and committing suicide on day K+2.

Proof: Suppose I see K+1 blue-eyed persons, then I have two hypotheses, namely that there are K+1 or K+2 blue-eyed persons. Distinguishing between these two cases is equivalent to discovering my own eye color. By assumption, I do not discover anything on days 0 through K, nor do I commit suicide on days 1 through K+1, for the reason that it would be equivalent to seeing anywhere from 0 to K blue-eyed persons — a contradiction.
On day K+1, suppose I still did not discover my eye color. Here there would be two cases: if there were exactly K+1 blue-eyed persons, then each of them would see K blue-eyed persons, but by assumption, they would commit suicide on day K+1, so I would discover my own eye color to be brown — a contradiction; so there must be K+2 blue-eyed persons, then again, I would discover my own eye color (blue) — a contradiction. Therefore, it must be the case that I discover my own eye color on day K+1 and commit suicide the following day.

In the converse, suppose I discover my eye color on day K+1 but not before. Then the visitor’s statement and all my observations from days 1 to K are not informative, but the one on day K+1 is informative. By assumption, on each day k for k from 1 to K+1, those who see k-1 blue-eyed persons commit suicide. In particular, consider the action of blue-eyed persons on day k: it communicates whether there are k blue-eyed persons in total (if they commit suicide) or not (if they do not).* Now, anybody who sees B blue-eyed persons has two hypotheses: that there are B or B+1 blue-eyed persons. So the only way that day K+1 can be the first informative day to resolve these two cases, is if B=K+1 — for a smaller B, the question would be resolved on an earlier day; and for a larger B, the information up to day K+1 is insufficient. ∎

* It is easy to show that the action of brown-eyed persons on each day provides no additional information, conditioned on the action of blue-eyed persons on the previous day.

Taken together, we conclude that: on day 100 after the visitor’s statement, all blue-eyed islanders commit suicide; and on day 101, all brown-eyed islanders commit suicide.

This isn’t the end of the story, however, because while Proposition 1 is obvious enough, it remains perplexing that the visitor’s statement of something publicly known by all of the islanders since time immemorial results in anything at all. Why couldn’t the islanders have “filled in” for the visitor’s role somehow? What form of information did the visitor provide?

The answer is that the visitor brought a synchronization signal. There was no time origin in the islanders’ “history,” which goes back to negative infinity. Since the entire inference exercise depended on everybody counting days from a common “day 0,” they couldn’t align themselves without a common signal.

(Some further explanations of this puzzle here
and here, where the synchronization can also be interpreted as between all “levels” of inferential belief by each islander — this is the mechanism by which a statement about the world prompts each islander to start “counting” in the first place; after all, the visitor never explicitly asks the islanders to synchronize to anything, nor do the islanders have an agreed upon protocol to coordinate.)

There is a similar problem of this flavor:

Suppose there are some beasts who like to eat meat, but if they eat any meat, they themselves turn into a piece of meat (still “alive,” but liable to be eaten by other beasts). Presuming the beasts would all like to survive foremost (even as meat), and eat meat if they can get away with it, what would happen if there were, say, 100 beasts and 1 piece of meat?

The answer is that when there is an odd number of beasts, one of the beasts will eat the meat; when there is an even number, all of them will refrain.