The Boss Room

These are the puzzles mathematicians tell each other. Each has stopped a common room full of professionals; several have grown academic literatures; the last has resisted every proposed resolution for nearly eighty years and closes the chapter still open. The ratings here read ★★★★ and ★★★★★, and they measure depth, not prerequisites — nothing in this room needs more than arithmetic. What each puzzle demands is a move that is probably not in the kit yet, executed down a long chain with zero leaks.

The room has rules. One puzzle per sitting. Read a statement, then close the book and carry the problem for a day before reading on: the value is manufactured during the attempt, not at the answer. Solving one of these cold is rare, and it is not the bar. The bar is meeting each solution with enough failed approaches behind you that the key idea, when it arrives, answers a question you had actually asked. A boss studied transfers nearly as well as a boss beaten.

One observation before the door opens. Nearly every scenario here threatens its characters — prisoners, pirates, islanders bound by a decree, a condemned man. The genre is being honest about the altitude: at this level there is no partial credit. Six of the seven solutions below are airtight, certainty by construction. The seventh trades certainty for a 31 percent miracle — and then proves that no strategy on earth does meaningfully better.

★★★★ 8 · The Twelve Balls

Twelve visually identical balls; exactly one is off-weight — heavier or lighter, unknown which. A balance scale, and three weighings only. Identify the odd ball and whether it is heavy or light, guaranteed.

This one repays a full evening. Give it one.

Solution. Before any cleverness, budget. There are 24 possible answers: twelve balls, each possibly heavy or light. A weighing has exactly three outcomes — left heavy, right heavy, balance — so three weighings distinguish at most 3³ = 27 futures, while two manage only 9. Three is the floor, and 24 ≤ 27 says the floor is barely enough: no weighing may waste information. After every outcome the surviving cases must number at most 9, then 3, then 1.

That arithmetic designs the first move by itself. Weigh six against six and balance is impossible: a tilt is certain, twelve cases survive it, and twelve cannot fit through the 9 futures two weighings offer. Dead before starting. Five against five? A tilt leaves ten. Dead. Four against four: a tilt leaves eight (four suspects of heaviness, four of lightness), and balance leaves eight (four untouched balls, either direction). Alive everywhere. The information bound forced the 4–4 split before ingenuity was even consulted.

First weighing: {1,2,3,4} against {5,6,7,8}.

If it balances — the odd ball is among 9–12, eight cases. Second weighing: {9,10,11} against {1,2,3}, three suspects against known-good ballast. Balance → 12 is odd; weigh 12 against any good ball to read its direction. Left heavy → one of 9, 10, 11 is heavy; weigh 9 against 10 — the heavier pan names it, balance convicts 11. Right heavy → the same three are light suspects; mirror.

If the left side sinks — either 1–4 is heavy or 5–8 is light, eight cases. The second weighing must mix suspects across the pans: {1,2,5} against {3,4,6}, parking 7 and 8. Balance → 7 or 8 is light; weigh 7 against 8, and the lighter is guilty (they cannot balance). Left sinks again → 1 or 2 heavy, or 6 light; weigh 1 against 2 — heavier is guilty, balance convicts 6 light. Right sinks → 3 or 4 heavy, or 5 light; weigh 3 against 4 — heavier is guilty, balance convicts 5 light. Count the branches: 2 + 3 + 3 = 8. Every case lands.

If the right side sinks — the mirror image.

Two ideas carried the design. Cleared balls become instruments — known-good ballast that lets three suspects be weighed against "truth." And suspects rotate between pans so that each outcome splits the survivors nearly in three. This is the problem wartime mathematicians joked about air-dropping over Germany to paralyze enemy research; Freeman Dyson's systematic analysis ran in the Mathematical Gazette, 1946 — information-theoretic thinking two years before Shannon gave it a name.

The Move — Maximize information per test. Budget outcomes before designing experiments, then shape every test so its outcomes are as equally loaded as possible. This is experiment design in miniature, and it reappears wherever questions cost money: debugging, medical triage, twenty questions of every kind.

★★★★ 44 · The Pirate Game

Five perfectly rational pirates, strictly ranked: A most senior, then B, C, D, E. They must divide 100 gold coins. The most senior pirate proposes a split; all five vote; a tie passes, the proposer's vote carrying. If the proposal fails, the proposer is thrown overboard and the next in rank proposes. Every pirate's priorities, in order: survive; then maximize gold; then, all else equal, enjoy seeing a rival thrown overboard. What does A propose?

Take your time. The gold isn't going anywhere.

Solution. Forward reasoning drowns — "what will B do, which depends on what C would do, which depends…" spirals without anchor. Anchor at the end, where the game is trivial, and roll back.

Two pirates left (D, E): D proposes 100–0 for himself, votes yes, and the tie passes. E's opinion is decorative.

Three (C, D, E): if C dies, D's reign gives E nothing — so E's vote costs exactly one coin, which beats D's promised nothing (the bloodlust tiebreak only applies all else equal). C proposes 99–0–1 and it passes 2–1. D cannot counterbid: his own next-round future is 100, so C never buys him.

Four (B, C, D, E): if B dies, C's regime pays D zero. D is now the cheap vote: 99–0–1–0 passes 2–2 on B's casting vote. Buying E instead would cost 2, since E already collects 1 under C.

Five: if A dies, B's plan pays C zero and E zero. A needs three votes of five — his own plus two others — and the two paupers-under-B are exactly C and E, one coin each. A proposes 98–0–1–0–1, and it passes 3–2.

The shock is the direction. The most exposed player — first to face the plank — captures 98 percent, while the pirates with "obvious" leverage collect one coin or none. Voting rules plus common knowledge of rationality allocate power in ways no intuition about seniority predicts. A second lesson comes cheaper here than in a live negotiation: the theorem is fragile. Real humans reject insulting offers out of spite — ultimatum-game experiments show it reliably — so backward induction holds exactly as far as its premises do. Know when the game is pirates and when it is people. The problem is economics folklore; the canonical telling is Ian Stewart's "A Puzzle for Pirates," Scientific American, May 1999, crediting Stephen Omohundro.

The Move — Solve the endgame first. Anchor at the final subgame, where the answer is trivial, and roll toward the present, pricing every vote at its owner's alternative future. Chess endings, contract design, and any negotiation with a walk-away run on this engine.

★★★★ 9 · 100 Prisoners and a Light Bulb

One hundred prisoners. One interrogation room holding a single light bulb, initially off. Each day the warden brings one prisoner, chosen uniformly at random, to the room; the prisoner may toggle the bulb or leave it alone. At any moment, any prisoner may declare: "All one hundred of us have visited this room." If the claim is right, everyone goes free; if wrong, everyone dies. The prisoners may confer once, before the first visit. Find a strategy that cannot be wrong.

Design your own protocol before reading theirs.

Solution. The room's shared memory is one bit. Nobody can count in it — but a hundred people can talk through it, if they fix in advance who says what, and when. Appoint one prisoner the Counter. Everyone else follows a single rule: the first time you enter and find the bulb off, switch it on — once in your life; in every other circumstance, touch nothing. The Counter's rule: whenever he finds the bulb on, he switches it off and adds one to a private tally. When the tally reaches 99, he declares.

Correctness is absolute, not probable. Each on-to-off cycle the Counter records corresponds to exactly one distinct non-counter's first-and-only signal: nobody signals twice, and no signal can be lost, because only the Counter ever switches the bulb off. Tally 99 therefore means 99 distinct others have visited — and the Counter himself makes 100. The bulb is a one-bit channel; the protocol serializes 99 messages through it, one at a time.

The price is patience. Simulation puts the expected wait near 10,300 days — twenty-eight years — most of it spent with the bulb burning idle, waiting for the Counter's next random visit. Faster protocols exist: multi-stage schemes in which prisoners carry "tokens" of escalating denomination cut the expected time substantially (the family is analyzed by Dehaye, Ford & Segerman, Mathematical Intelligencer, 2003). But the single-counter scheme is the canonical proof of possibility, and its correctness argument fits in four sentences — its own kind of optimal. The puzzle is young for a classic: first posted to the newsgroup rec.puzzles on 24 July 2002.

The Move — Design a one-bit protocol. When shared state is tiny, stop asking "what can I deduce?" and ask "what protocol can we agree on beforehand?" Designate an aggregator; make every signal single-shot and unambiguous. This is distributed-systems engineering told as a fable.

★★★★★ 37 · 100 Prisoners and 100 Boxes

The same hundred prisoners, a crueler room. One hundred boxes in a row; inside them, the numbers 1 to 100 in a uniformly random permutation, one per box. Each prisoner, alone, may open fifty boxes in search of his own number. The room is then restored exactly as it was, and he leaves by another door, able to signal nothing. If every prisoner finds his own number, all go free; a single failure kills them all. Opening boxes at random, each prisoner succeeds with probability 1/2, so the group survives with probability (1/2)¹⁰⁰ ≈ 8 × 10⁻³¹ — call it never. There exists a strategy whose survival probability exceeds 31 percent. Find it.

Read that again: from 10⁻³⁰ to nearly one in three. Now hunt.

Solution. No communication is possible, so the coordination must be smuggled through the only shared structure that exists: the contents of the boxes themselves. The cycle strategy: prisoner k opens box k first. It contains some number j; he opens box j next; reads m there, opens box m — following the pointers. That is the entire strategy.

Why it works: box-to-content is a permutation, and every permutation decomposes into cycles. Starting at box k and following pointers walks exactly the cycle containing k, and that walk is guaranteed to reach the box holding the number k — the pointer that closes the loop. So prisoner k succeeds precisely when his cycle is no longer than fifty. His fate stops being fifty independent gambles and becomes one question about the permutation's shape.

With that, the group's fate collapses onto a single global event: all hundred succeed if and only if the permutation contains no cycle longer than 50. How likely is a long cycle? For any length k > 50, at most one such cycle can exist (two would need more than 100 elements), and the probability that a random permutation of 100 contains a k-cycle is exactly 1/k. So the probability of failure is 1/51 + 1/52 + ⋯ + 1/100 = H₁₀₀ − H₅₀ ≈ ln 2 ≈ 0.693, and survival is 1 − (H₁₀₀ − H₅₀) = 0.31183, computed exactly. The number barely degrades as the prison grows: the limit is 1 − ln 2 ≈ 30.7 percent, whether the prisoners number one hundred or one billion.

Now the part to sit with. Ask any single prisoner what the strategy did for him: the cycle through his box is equally likely to have any length from 1 to 100, so his personal success probability is 50/100 — exactly 1/2, identical to random guessing. No individual's odds improved at all. What changed is the correlation. Random guessers fail independently, so someone almost surely fails; cycle-followers fail together or not at all, because every member of a too-long cycle fails at once and, when no long cycle exists, nobody does. The strategy herds a hundred fates onto one coin flip about the shape of a single permutation. And it is essentially unbeatable: Curtin and Warshauer (2006), building on the original analysis of Miltersen and Gál, showed no strategy does meaningfully better.

The problem was born in theoretical computer science — Peter Bro Miltersen posed it (with Anna Gál) at ICALP 2003 as a gadget in a data-structure lower bound, and his colleague Sven Skyum found the cycle strategy. It has been called, credibly, the most counterintuitive result in recreational mathematics.

The Move — Correlate your fates. When independent successes multiply into doom, redesign so that everyone succeeds or fails on the same event. A second move rode along: impose structure on randomness — the permutation's cycle decomposition was sitting there all along, waiting for someone to read boxes as pointers.

★★★★★ 10 · The Blue-Eyed Islanders

An island of two hundred perfect logicians: one hundred blue-eyed, one hundred brown-eyed. There are no mirrors and no reflective water, and eye color is never discussed — a taboo with teeth. Everyone sees everyone else's eyes; no one knows their own. The law: on the midnight after you know your own eyes are blue, you must leave the island forever. All of this — the law, everyone's perfect logic — is common knowledge. One day a visitor addresses the entire island at once: "I see at least one person with blue eyes." Every islander could already see at least ninety-nine blue-eyed people; the visitor seems to have said nothing new. What happens?

What did the visitor actually add? Sit with that.

Solution. All one hundred blue-eyed islanders leave together, at midnight of the hundredth day.

Climb from the bottom. One blue-eyed islander: she sees no blue eyes anywhere, so the announcement can only mean her. She leaves the first midnight. Two: each sees exactly one blue-eyed person and reasons, "if my eyes are brown, he is alone — he will work it out and leave tonight." Nobody leaves, because each was waiting on the other. That silence is loud: each now knows there is a second pair of blue eyes, and whose. Both leave the second midnight. Three: each blue-eyed islander sees two and reasons, "if I am brown, those two resolve each other by night two." Midnight two passes, full island. All three know; they leave night three. The induction is on rails: n blue-eyed islanders leave on midnight n. With one hundred — ninety-nine silent midnights, then a mass departure on the hundredth.

But what did the visitor add? Everyone already saw blue eyes. Here is the honest answer, and it is the entire puzzle: before the announcement, "someone has blue eyes" was known to everyone — but it was not common knowledge. Follow the nesting. A blue-eyed islander sees 99 others. He knows each of those sees at least 98. He knows they know that the others see at least 97… Each level of "everyone knows that everyone knows" burns one islander of margin, and at depth 99 the chain bottoms out in a hypothetical islander who — inside all those nested imaginations — might see no blue eyes at all. The 99-deep statement was false. The visitor's announcement — heard by all, seen by all to be heard by all — makes "someone has blue eyes" true at every depth simultaneously. That is what was new: not a fact about eyes, a fact about knowledge of knowledge.

From then on, each silent midnight is itself a public announcement — "nobody yet knew" — and the induction climbs one rung per night until it reaches the truth. A public statement can change the world while adding zero first-order information. The puzzle descends from Littlewood's dirty-faces problem (A Mathematician's Miscellany, 1953) and Gamow and Stern's forty unfaithful wives (Puzzle-Math, 1958); the blue-eyed dress of it spread through the 2000s, notably via xkcd and Terence Tao's 2008 blog treatment.

The Move — Induct on common knowledge. "Everyone knows X" and "everyone knows that everyone knows X…" are different states of the world, and protocols, markets, and standoffs run on the difference. When a public event changes behavior without changing anyone's private facts, look for the depth of knowledge it completed.

★★★★★ 49 · Freudenthal's Impossible Puzzle

Two integers x and y are chosen, with 1 < x < y and x + y ≤ 100. Mr. P is told only their product; Mr. S is told only their sum. The following conversation takes place, every word truthful and heard by both:

P: "I don't know the numbers." S: "I knew you didn't." P: "Now I know them." S: "Now I know them too."

Find x and y — from the dialogue alone.

It has been called the impossible problem. It isn't — quite.

Solution. Not one word refers to the numbers, yet each line is a hard fact about what a speaker's information allows — and each fact filters the candidate pairs.

Line 1 — P doesn't know. His product must factor ambiguously within the constraints. Had it been, say, 35 = 5 × 7, two primes, he would have known at once. Every uniquely-factorable product dies here.

Line 2 — S knew P didn't. Not guessed: knew, from the sum alone. So every admissible split of S's sum must give an ambiguous product. This is savage. Any sum splittable into two primes fails — that split's product would have told P everything — and at this size every even sum can be so split (checked directly; no conjecture needed). Sieving the odd survivors leaves exactly ten sums: {11, 17, 23, 27, 29, 35, 37, 41, 47, 53}.

Line 3 — now P knows. Learning line 2 told P the sum lies in that ten-element list; his product must be compatible with exactly one member. Watch it work on the eventual answer: product 52 = 4 × 13, sum 17 — in the list; or 2 × 26, sum 28 — even, out. One survivor. P announces knowledge.

Line 4 — now S knows too. Among all splits of his sum, exactly one can have become P-solvable at line 3. Run his sum, 17: the split (2,15) has product 30 = 2 × 15 (sum 17, listed) but also 5 × 6 (sum 11, also listed) — that P would still be stuck, so (2,15) is eliminated. (3,14): product 42, ambiguous between sums 17 and 23. Out. (5,12): 60, torn between 17 and 23. (7,10): 70, torn between 17 and 37. (8,9): 72, torn between 17 and 27. (6,11): 66, torn between 17 and 35. Only (4,13) survives — so S, holding 17, now knows. And machine verification closes the loop: for every other sum in the list, two or more splits survive line 3, so line 4 would have been false. The sum is 17, the product 52: x = 4, y = 13.

A dialogue that looked content-free determined two numbers uniquely. Chapter 5's Cheryl's Birthday is this puzzle's pop-viral descendant, running the same engine at lower voltage. Hans Freudenthal published the original in Nieuw Archief voor Wiskunde, 1969; Gardner anglicized it a decade later as "the impossible problem" — impossible-seeming, because declared ignorance looks like the absence of information.

The Move — Mine the meta-statements. "I don't know" and "I knew you didn't" are mathematical facts about information sets — filters as sharp as equations. When a negotiator, a market, or a machine announces what it cannot yet conclude, that announcement is data. Nothing was said about the numbers, and that was the data.

★★★★ 50 · The Unexpected Hanging

A judge decrees on Sunday: "You will be hanged at noon on one weekday this coming week — and the hanging will be a surprise. You will not know the day beforehand." The prisoner reasons: "They cannot hang me Friday: by Thursday night, with four days gone, I would know it was coming. Friday is out. But with Friday struck, Thursday becomes the last possible day, so by Wednesday night I would know — Thursday is out too." Day by day the week collapses, and the prisoner concludes, relieved, that the sentence cannot be carried out at all. On Wednesday at noon the hangman arrives. The prisoner is completely surprised. The decree, in the end, was true. Where is the flaw in his reasoning?

Nearly eighty years of philosophy has not settled this one.

Solution. There isn't one — not a settled one — and this book will not pretend otherwise. What is agreed: the prisoner's elimination argument and the judge's eventual vindication cannot both be sound, and the fault must sit somewhere in the reasoning about knowing. Where, exactly, remains contested across more than fifty academic papers.

Three families of diagnosis, none of them consensus. Quine (1953) attacked the base of the induction: eliminating Friday requires the decree to be not merely true but knowably reliable at every future point — and "the decree will be fulfilled" versus "I may lean on the decree inside my own reasoning" are different claims, silently conflated. The epistemic-logic school formalizes "surprise" with knowledge operators and finds the announcement self-referentially unstable: a statement that can be true yet not knowably true, so that the prisoner's own use of it destroys it — Sorensen (1988) calls the final-day case a "blindspot." The deflationary school shrugs: for a one-day week the decree is flatly inconsistent, for five days it is approximately assertable, and intuition smears the difference into an aura of paradox.

The problem reportedly began life as a Swedish wartime civil-defense announcement — a drill to be held next week, on a day no one could predict — and was chewed over until D. J. O'Connor put it into Mind in 1948. Gardner's 1963 column made it famous; Sorensen's Blindspots (1988) gave it a book. The ledger stays open.

Why end the boss room on an unbeaten boss? Because the genre should be honest about its edges, and because the lesson survives the missing solution. Every other puzzle in this room ran on knowledge behaving lawfully — counted through a bulb, nested on an island, mined from a dialogue. Here is the door marked knowledge about one's own future knowledge, and behind it the floor is missing. The honest response to an open problem is the sentence this book has tried to earn the right to say plainly: nobody knows yet.

The Move — Knowledge can self-destruct. Statements about what you will know are not ordinary facts; feeding them into your own inference can invalidate them. Respect the type-difference between what is true and what is knowably true — announcements of the form "you will be audited, unannounced" carry real weight in law and security, and this puzzle is the standing proof that they can be built on air.

The moves you now own

• Maximize information per test (★★★★ 8, the twelve balls) — budget outcomes first (3³ ≥ 24), then make every test split the survivors evenly.
• Solve the endgame first (★★★★ 44, the pirates) — anchor where the game is trivial; roll backward, pricing each vote at its alternative future.
• Design a one-bit protocol (★★★★ 9, the light bulb) — tiny shared state calls for a pre-agreed protocol, not deduction; appoint an aggregator.
• Correlate your fates (★★★★★ 37, the boxes) — when independent success is hopeless, hang everyone's success on one shared event.
• Induct on common knowledge (★★★★★ 10, the islanders) — "everyone knows" and "everyone knows everyone knows" are different worlds.
• Mine the meta-statements (★★★★★ 49, Freudenthal) — declared ignorance is data; filter on information sets.
• Knowledge can self-destruct (★★★★ 50, the hanging) — truths about future knowledge may not survive being used.

These seven are Part II's summit ridge. Beyond their individual moves, they train a temperament: patience with long chains that must not leak, respect for answers that offend intuition and are true anyway, and — once, at the end — the composure to leave a question open because it is open. Part III visits the people who climb grades like this for sport, and takes their training apart.