INKWIRE(7) reasoning puzzles INKWIRE(7)
census
The Census of Liars
Everyone already knows, and yet nothing happens until it is said aloud.
NAME
Problem
An island has one hundred inhabitants arranged in a single circle. Every inhabitant can see everyone else's forehead but not their own. Each forehead is marked with either a dot or a blank, and you can see other people's marks perfectly.
Everyone knows the rule: if you can deduce that your own forehead carries a dot, you must leave the island that night, and you will be correct. Nobody can communicate after the announcement.
Ninety-nine inhabitants have dots and one has a blank. A visitor arrives and says one true sentence to the whole group: "At least one of you has a dot." Then the visitor leaves. What happens, and on which night?
SIGNALS
Conditions and what each one forces
| # | Condition | What it forces |
|---|---|---|
| 1 | Everyone sees all other foreheads | Each dotted inhabitant sees exactly 98 dots; the blank inhabitant sees 99 |
| 2 | Each knows the rule and reasons perfectly | Behaviour can be predicted by induction on the number of dots a person sees |
| 3 | "At least one dot" was already known to all | The sentence adds no first-order fact; its entire contribution is that it is now known to be known to be known, indefinitely |
| 4 | Nobody can signal or confer | The only update channel is each night's departure pattern, which is itself common knowledge |
| 5 | Exactly one inhabitant is blank | The 99 dotted inhabitants each see 98 dots, so the induction runs to depth 98 and they all leave on night 98 |
EXAMPLES
Method
Induction on what each person sees. The visitor's sentence does not add information about dots; it adds a floor to the depth of knowledge that everyone can rely on others to have.
[+] Worked solution 4
Start with one dot. An inhabitant seeing zero dots hears "at least one" and knows immediately that it is them. They leave on night one.
With two dots: each dotted person sees one dot and reasons "if I were blank, that person would be the only dotted one and would leave tonight". When nobody leaves on night one, both conclude they are dotted and leave on night two.
The pattern generalises: with n dots, all n dotted inhabitants leave on night n, because each of them sees n−1 dots and waits n−1 nights for the departure that would have settled the case if they themselves were blank. Here n = 99, so on the ninety-ninth night all ninety-nine dotted inhabitants leave together, and the blank one stays.
The blank inhabitant sees 99 dots, which is consistent with being dotted themselves only if n were 100 — and n = 100 is ruled out for them by the fact that nobody left on night 98. Their reasoning is exactly right, and it tells them they are blank, which is why they are the one who stays.
Kindred entries
- [P] twelve-coin One coin is counterfeit and you do not know if it is heavy or light.
- [P] blue-eyes A rule, a mirror-free island, and one sentence that changes everything.
- index — /t/puzzle/
[+] Notes and objections 3
- What exactly does the announcement change?
- It creates a base case. Without it, the chain "if I were blank, then that person would see no dots and leave tonight" has no starting point, because nobody is sure the chain bottoms out. The announcement supplies the trivial case that the induction rests on.
- Why does it take 99 nights rather than one?
- Because each level of the induction has to be observed rather than assumed. Each night without a departure is evidence that pushes everyone's minimum estimate of the dot count up by one.
- Does the visitor need to be right?
- Yes. If the statement were false, the first night's expected departure would not occur and the induction would collapse on the second day instead of running. A false announcement produces no coordinated behaviour.
Scope — Puzzle presented for practice; the induction above is stated for general n.