The Muddy Children Puzzle

$n$ children play together; $k$ of them get mud on their forehead. Each child can see everyone else's forehead but not their own, and no one is allowed to tell anyone else whether they're muddy. A parent announces, truthfully and publicly: "At least one of you has a muddy forehead." Then the parent repeats, every minute: "If you know you're muddy, step forward now." Nothing happens for $k-1$ rounds — and then, on round $k$, all $k$ muddy children step forward simultaneously. Nobody told them anything they didn't already know by looking around. What changed?

The core idea: public versus private knowledge

Before the announcement, if $k \ge 2$, every child already knows — as a fact — that at least one child is muddy, simply by looking at the others. The announcement tells nobody a new fact. What it creates is common knowledge: not just "everyone knows it" but "everyone knows that everyone knows it, and everyone knows that, and so on" without limit. That infinite tower of "knows-that-you-know" is exactly what's missing beforehand, and it's what the repeated silent rounds slowly build.

Working through small cases

$k=1$ muddy child. That one child sees zero muddy foreheads among everyone else. The announcement "at least one is muddy" combined with seeing nobody else muddy immediately tells them it must be themself. They step forward on round 1.

$k=2$ muddy children, call them A and B. Each sees exactly one muddy forehead (the other's) and, before the announcement, could imagine two scenarios: "I'm clean and only the other is muddy" or "we're both muddy." The announcement doesn't resolve this by itself. But now reason about round 1: A thinks, "if I were clean, B would see zero other muddy children, know the announcement means them, and step forward on round 1." When round 1 passes with nobody stepping forward, A learns that B did not see zero muddy foreheads — meaning A themself must be muddy too. B reasons symmetrically. Both step forward together on round 2.

General $k$. By induction, if only $k-1$ children were muddy, they would all deduce it and step forward on round $k-1$ using exactly the round-$(k-1)$ version of this argument applied to what each of them observes. When round $k-1$ passes with no one stepping forward, every muddy child among the true $k$ learns that the number of muddy foreheads they can see (namely $k-1$) is not the true count — so they themselves must add one more, making the true count $k$, and they step forward on round $k$.

What this means in practice

This puzzle is the cleanest introduction to why "everyone already knows X" is not the same as "it's common knowledge that X" — a distinction that matters directly in markets. A piece of news that every trader has individually seen doesn't move a price until it becomes common knowledge that everyone has seen it and is trading on it; that's why a headline can sit unpriced for minutes until an official announcement, a print in size, or an exchange notice makes the information common rather than merely widespread. Interviewers use this puzzle to test whether a candidate can reason about layered belief ("I know that you know that I know...") rather than stopping at the first level.