xxvii. Blue-Eyed Islanders and Muddy Children

Problem. On an island live perfect logicians; $k\ge 1$ of them have blue eyes, the rest brown. Nobody knows their own eye colour, there are no mirrors and no talking about eyes; anyone who learns their own colour must leave at midnight, and everyone sees who left. One day a visitor announces publicly: “at least one of you has blue eyes”. What happens?

Answer. Nothing for $k-1$ nights; on night $k$ all blue-eyed islanders leave. (If everyone also knows that only blue and brown exist, the brown-eyed leave on night $k+1$.) For $k\ge 2$ the visitor told everyone something they already knew; what changed is that it became common knowledge.

Muddy children is the same puzzle: $k$ of $n$ children have mud on their foreheads, the father says “at least one of you is muddy” and asks repeatedly “do you know whether you are muddy?”; the muddy children answer “yes” in round $k$.

Notion	Meaning	With $k$ blue-eyed islanders before the announcement
$\phi$	”someone has blue eyes”	true
$E\phi$ (mutual knowledge)	everyone knows $\phi$	true iff $k\ge 2$
$E^j\phi$	everyone knows that everyone knows … ($j$ times)	true iff $j\le k-1$
$C\phi$ (common knowledge)	$E^j\phi$ for every $j$	false; the announcement makes it true

The code below models knowledge explicitly with possible worlds (Kripke semantics): a world is a bitmask of eye colours, islander $i$ cannot distinguish $w$ from $w\oplus 2^i$, and public events delete worlds.

// eyes[i] = 1 blue, 0 brown; only these two colours exist (common knowledge). After "someone is blue",
// every islander who knows their colour leaves that night; departures are public. Returns each one's night (0 = stays).
vector<int> leaveNights(const vector<int>& eyes) {
    int n = sz(eyes), W = 1 << n, actual = 0;
    for (int i = 0; i < n; i++) actual |= eyes[i] << i;
    vector<char> possible(W, 1); possible[0] = 0;             // the announcement deletes the all-brown world
    vector<vector<int>> hist(W);                              // public departure history if w were the real world
    vector<int> gone(W, 0), night(n, 0);
    for (int d = 1; d <= n + 1; d++) {
        vector<int> leave(W, 0);
        for (int w = 0; w < W; w++) if (possible[w])
            for (int i = 0; i < n; i++) if (!(gone[w] >> i & 1)) {
                int v = w ^ 1 << i;                           // the only world islander i cannot rule out by sight
                if (!possible[v] || hist[v] != hist[w]) leave[w] |= 1 << i;   // v is excluded: i knows
            }
        for (int w = 0; w < W; w++) if (possible[w]) hist[w].push_back(leave[w]), gone[w] |= leave[w];
        for (int i = 0; i < n; i++) if (leave[actual] >> i & 1) night[i] = d;
    }
    return night;
}

Proof: the blue-eyed leave on night k

Work in the possible-worlds model of the code: islander $i$ in world $u$ knows their colour on night $j$ iff the alternative $u\oplus 2^i$ was deleted by the announcement or had a different departure history on nights $\mathrm{1..}j-1$.

(P) Nobody leaves early. For every $j\ge 0$: in every world with at least $j+1$ blue-eyed islanders, nobody leaves on nights $\mathrm{1..}j$. Induction on $j$; $j=0$ is empty. Let $u$ have $m\ge j+1$ blue and fix islander $i$. The alternative $u^{\prime }=u\oplus 2^i$ has $m\pm 1\ge j$ blue, so it is not the deleted all-brown world, and by the hypothesis for $j-1$ nobody leaves on nights $\mathrm{1..}j-1$ in $u$ or in $u^{\prime }$. The histories agree, so on night $j$ islander $i$ cannot rule out $u^{\prime }$ and stays.

(Q) The blue-eyed leave on night $m$. Induction on the number $m\ge 1$ of blue-eyed. By (P) nobody leaves on nights $\mathrm{1..}m-1$. A blue islander $b$ considers $u^{\prime }=u$ with $b$ brown, which has $m-1$ blue: if $m=1$, $u^{\prime }$ is the deleted world; otherwise, by (Q) for $m-1$, the blue-eyed of $u^{\prime }$ leave on night $m-1$, whereas in $u$ nobody did. Either way $b$ knows on night $m$. A brown islander considers a world with $m+1$ blue, where by (P) nobody leaves on nights $\mathrm{1..}m$; its history up to night $m-1$ equals that of $u$, so they stay on night $m$.

Brown on night $m+1$ (two-colour knowledge): the brown islander’s alternative has $m+1$ blue and, by (P), no departure on night $m$, but in $u$ the blue-eyed left on night $m$. The histories differ, so they know their colour is not blue, hence brown. Without the two-colour assumption they only learn “not blue” and stay forever.

The function checks this world by world: verified for every eye assignment with $n\le 9$ (blue leave on night $k$, brown on night $k+1$, nobody earlier).

Proof: before the announcement, E^(k-1) holds but E^k does not

In the possible-worlds model, $E^j\phi$ holds at $w$ iff $\phi$ holds at every world reachable from $w$ by $j$ steps, where a step from $u$ goes to $u\oplus 2^i$ for some islander $i$ (what $i$ considers possible). Each step changes one bit, so after $j$ steps from a world with $k$ blue there are at least $k-j$ blue; for $j\le k-1$ at least one remains, so $E^{k-1}\phi$ holds. For $j=k$, let the blue-eyed $b_1,\dots ,b_k$ flip their own bits one after another: the chain reaches the all-brown world, where $\phi$ is false; so $E^k\phi$ fails. The announcement deletes the all-brown world from the model, which is exactly what makes $E^k\phi$ (and $C\phi$) true, and exactly what the induction above uses at its base.

Related notes

• Proof Techniques (induction)
• Prisoners and Hats
• Sum and Product Puzzle (another knowledge puzzle)