Pure Deduction

Deduction puzzles hide nothing. Every fact you need is on the table from the first sentence; there is no trick frame to break, no pun to catch. The entire difficulty is discipline: holding a lattice of constraints in working memory, milking each fact completely before touching the next, and — above all — never confusing what you know with what you merely assume. Guessing before the forced moves are exhausted is the cardinal sin of this chapter, and nearly everyone commits it.

You have already done deduction's cousin once in this book: the wolf, the goat, and the cabbage back in Chapter 1 were state-space planning — mapping legal moves through a maze of constraints. This chapter turns from planning to inference. The material rises in a deliberate ladder: first liars and truth-tellers (the atom of case analysis), then wrongness as information, then the grand grid of the zebra puzzle, then puzzles where the data is other people's ignorance, and finally deduction against a clock.

One promise before we start. Each solution below teaches the path — including the wrong turns a smart solver actually takes — because in deduction, the method is the entire prize. The answers themselves are famously useless: nobody needs to know who owns a zebra.

Truth machines

Raymond Smullyan built a whole logical education (What Is the Name of This Book?, 1978) on one island: knights always tell the truth, knaves always lie. The setting sounds like a joke. It is actually a laboratory where every utterance becomes an equation.

★ 2 · Knights and Knaves: "We Are Both Knaves"

Statement. On an island, knights always tell the truth, knaves always lie. A says: "We are both knaves." What are A and B?

Pause here. The page can wait.

Solution. Run the only two cases. Suppose A is a knight: then his statement is true, so both are knaves — including A. Contradiction; knights don't lie. So A is a knave, and his statement is therefore false: they are not both knaves. Since A is one, B must be the knight. A = knave, B = knight.

Savor the fine grain, because it trips people for years afterward: a knave can say "we are both knaves" — precisely because the statement comes out false. He is lying about the pair, truthfully to his nature. The statement is not about what a knave would never say; it is about what must be false when he says it.

The Move — Assume, then break it. Hypothesize each case and let self-contradiction do the elimination. This is the atom of all logical deduction — proof by contradiction in its smallest wearable size.

★★ 4 · The Fork in the Road

Statement. A fork: one road to freedom, one to doom. Two guards, one always lies, one always tells the truth — you don't know which is which. One question, to one guard. What do you ask?

Stop and try to build the question yourself. It's buildable.

Solution. The false start: ask something factual ("Which road is freedom?") and you learn nothing, because you can't calibrate the answer without knowing the speaker. The insight is that you don't need to identify the liar — you need to route your question through both guards at once. Ask either guard: "If I asked the other guard which road leads to freedom, which would he point to?" — then take the opposite road. Check both cases: the truth-teller truthfully reports the liar's lie; the liar lies about the truth-teller's truth. Either way the answer passes through exactly one lie, so both guards point wrong — reliably.

Smullyan's compact single-guard variant does the same with logical machinery: "Are you a knight if and only if this road leads to freedom?" Biconditionals also force the lie to cancel.

The Move — Fold the lie onto itself. You cannot remove an unknown distortion, but you can route the signal through it twice — or pair it against itself — so it cancels. Experimental science does the same thing and calls it differential measurement. (Provenance for the curious: folklore, with an early formal relative in Nelson Goodman's 1931 note; popularized by Smullyan and, for a generation of children, by the film Labyrinth, 1986.)

★★ 3 · The Three Mislabeled Boxes

Statement. Three boxes: one holds only apples, one only oranges, one a mix. They are labeled APPLES, ORANGES, MIXED — and every label is wrong. Drawing as few fruits as possible (no peeking), relabel all three correctly. How many draws?

One fruit? Two? Work it out before reading.

Solution. One draw suffices — but only from the right box: the one labeled MIXED. Its label is wrong, so that box is pure. Draw one fruit; say it's an apple. Then the box labeled MIXED is the apple box. Now the forced chain: the box labeled ORANGES cannot contain oranges (wrong label) and cannot contain apples (taken) — so it is the mixed box. The box labeled APPLES gets what remains: oranges. Symmetric if you drew an orange.

The instructive false start is drawing from the box labeled APPLES. Wrong label means it holds oranges or mix — one draw may not settle which, and the deduction stalls. The move that feels least informative — sampling the "mixed" box — is the most informative, because that label's wrongness is total: it pins the box to exactly two possibilities, and one fruit splits them.

The Move — Total wrongness is information. "All labels are wrong" is not chaos; it is a strong constraint. A guaranteed error is exactly as informative as a guaranteed truth. (A 20th-century folklore staple, beloved of Gardner-era collections and tech interviews, and secretly a lesson in where to spend your first measurement.)

The grand grid

Now the full orchestra. The logic grid asks you to hold five interlocking categories in your head at once, and it punishes every leak. What follows is the most famous specimen — solved completely, every step shown, because this walkthrough is the curriculum.

★★★ 5 · The Zebra Puzzle ("Einstein's Riddle")

Statement. Five houses in a row, each with a distinct color, nationality, drink, cigarette brand, and pet. The classic clue list (the 1962 original counted "there are five houses" as clue one, which is why it advertises fifteen):

1. The Englishman lives in the red house.
2. The Spaniard owns the dog.
3. Coffee is drunk in the green house.
4. The Ukrainian drinks tea.
5. The green house is immediately to the right of the ivory house.
6. The Old Gold smoker owns snails.
7. Kools are smoked in the yellow house.
8. Milk is drunk in the middle house.
9. The Norwegian lives in the first house.
10. The Chesterfields smoker lives next to the man with the fox.
11. Kools are smoked next to the house with the horse.
12. The Lucky Strike smoker drinks orange juice.
13. The Japanese smokes Parliaments.
14. The Norwegian lives next to the blue house.

Who drinks water? Who owns the zebra?

This one deserves a table, a pencil, and half an hour. Take them.

Solution (unique — verified by exhaustive search). The path, with its two forks shown honestly:

Plant the anchors. Two clues are absolute: Norwegian in house 1 (clue 9), milk in house 3 (clue 8). Clue 14 then forces blue = house 2 — the Norwegian's only neighbor. Three cells down, no guessing yet.

Squeeze the colors. Green sits immediately right of ivory (clue 5): the pair fits as (3,4) or (4,5), since house 2 is blue. Meanwhile red hosts the Englishman (clue 1), so red isn't house 1 (Norwegian) or house 2 (blue).

Here is the first fork, and the first lesson in branch-killing. Try ivory = 3, green = 4. Then red and yellow fill houses 1 and 5; the Englishman bars red from 1, so red = 5, yellow = 1. Kools = 1 (clue 7), horse = 2 (clue 11). Coffee = 4 (clue 3). House 1 smokes Kools, so it can't be the Lucky-Strike-and-orange-juice house (clue 12), and the Norwegian isn't the tea-drinking Ukrainian — so house 1 drinks water, and tea and orange juice land in 2 and 5. House 5 is the Englishman, so the Ukrainian and his tea sit in house 2, orange juice and Lucky Strike in house 5. The Spaniard and the Japanese fill houses 3 and 4; the remaining cigarettes — Old Gold, Chesterfields, Parliaments — fill houses 2, 3, 4. Now the collapse: the Old Gold smoker owns snails (clue 6), but house 2 owns the horse, and whichever of 3 or 4 isn't the Parliaments-smoking Japanese is the Spaniard — who owns the dog. Nowhere for the snails. The branch dies. Cross it out with satisfaction: a dead branch is a fact.

So ivory = 4, green = 5, and coffee = 5. Red and yellow fill 1 and 3; the Englishman again bars red from house 1, so red = 3 (Englishman = 3), yellow = 1, Kools = 1, and the horse lives next door in house 2.

Propagate the drinks. House 1 smokes Kools, so not Lucky Strike, so no orange juice; the Norwegian is no Ukrainian, so no tea; milk and coffee are taken. House 1 drinks water. (First answer, and it arrived by pure elimination.) Tea and orange juice fill 2 and 4. A quick second fork: if the Ukrainian sat in house 4, orange juice would fall to house 2 along with Lucky Strike — leaving the Japanese, who smokes Parliaments, nowhere to sit among the remaining slots, and forcing the dog-owning Spaniard onto house 2's horse. Dead in two moves. So Ukrainian = 2, tea = 2, orange juice = 4, Lucky Strike = 4.

The last dominoes. Houses 4 and 5 take the Spaniard and the Japanese; Parliaments (clue 13) can't sit where Lucky Strike burns, so Japanese = 5, Spaniard = 4, dog = 4. Old Gold and Chesterfields remain for houses 2 and 3; snails follow Old Gold, and house 2 already keeps a horse — so Old Gold = 3, snails = 3, Chesterfields = 2. The fox lives next to the Chesterfields (clue 10): house 1 or 3; the snails hold house 3, so fox = 1. Four pets placed — the fifth cell is empty and waiting.

The Norwegian drinks the water; the Japanese owns the zebra — the two things the clues never mentioned, forced into existence by everything else.

The Move — Anchor, then propagate. Plant the absolute facts first, then squeeze every clue against the grid repeatedly; never branch while a forced move remains. And when you finally must branch, pick the cell with the fewest candidates and prosecute the branch to a quick death. This discipline — constraint propagation with lazy, reluctant branching — is exactly how modern SAT solvers earn their living.

Provenance, with a smile. This puzzle is universally sold as "Einstein's Riddle," sometimes with the garnish that "only 2% of people can solve it." Its actual birthplace: Life International magazine, December 17, 1962, no byline, solution and a list of successful solvers the following March. The grid mentions Kools, a cigarette brand of the 1930s, and ran seven years after Einstein died; the Lewis Carroll attribution drowns in the same bathtub. Einstein never saw it, 2% is marketing, and the puzzle needs neither — it is a masterpiece by an anonymous magazine staffer, which is somehow a better story.

Ignorance is data

The next rung looks impossible on first read: puzzles where people announce only what they don't know — and that turns out to be enough. The trick is to stop hearing "I don't know" as an apology and start hearing it as a mathematical statement about the speaker's information set.

★★★ 6 · Cheryl's Birthday

Statement. Cheryl gives Albert the month and Bernard the day of her birthday, chosen from: May 15, May 16, May 19, June 17, June 18, July 14, July 16, August 14, August 15, August 17. Albert: "I don't know when it is, but I know Bernard doesn't either." Bernard: "At first I didn't know, but now I do." Albert: "Then now I know too." When is Cheryl's birthday?

Resist the urge to skim. Each sentence is a filter — apply them in order.

Solution. The false start is trying to guess what Albert and Bernard are thinking. Don't. Translate each utterance into a fact about the candidate list, and cut.

Line 1, second half — "I know Bernard doesn't know." Bernard would know instantly only if his day were unique in the list: 19 (May only) or 18 (June only). Albert, holding just the month, is certain Bernard doesn't know — so Albert's month contains no unique day. May and June are eliminated wholesale. Left: July 14, July 16, August 14, August 15, August 17.

Line 2 — "At first I didn't know, but now I do." Bernard, holding the day, can now identify the date among the survivors — so his day appears exactly once in what remains. The 14 appears twice (July and August): gone. Left: July 16, August 15, August 17.

Line 3 — "Then now I know too." Albert, holding the month, is now certain — so his month contains exactly one survivor. August still holds two. July 16.

Notice what you just did: three sentences about not knowing pinned a single date out of ten, without anyone stating a fact about the birthday itself. Publicly declared ignorance is data. (And yes — the answer lands on a July 16, the very date on which this book's puzzle canon was compiled and verified. Coincidence, but the pleasing kind.)

The Move — Eliminate through others' knowledge. Each "I don't know / now I know" is a hard fact about the speaker's information set; apply it as a filter to the shared candidate list, in dialogue order. The same engine runs a five-star monster — Freudenthal's "impossible" sum-and-product puzzle — waiting in Chapter 7, alongside a hundred islanders who deduce their own eye color from silence itself.

Provenance. SASMO (Singapore & Asian Schools Math Olympiad), April 2015; it went globally viral via a Facebook post by TV host Kenneth Kong, briefly making epistemic logic the world's most argued-about topic at breakfast. The lineage runs straight back to Freudenthal's knowledge puzzles of 1969.

Deduction under a clock

Logic grids are static. The last rung adds scheduling — deduction about sequences of actions — where the trap is an assumption so reasonable it doesn't feel like an assumption at all.

★★★ 7 · The Bridge and the Torch

Statement. Four people must cross a rope bridge at night. The bridge holds at most two at a time; the group has one torch, and any crossing party must carry it. Crossing times: 1, 2, 5, and 10 minutes; a pair moves at the slower member's pace. Can everyone cross in 17 minutes?

The obvious answer is 19. Pause until 19 bothers you.

Solution. The greedy plan — the 1-minute walker ferries everyone, since returns should be cheap — gives: 1&10 across (10), 1 back (11), 1&5 across (16), 1 back (17), 1&2 across (19). 19 minutes, and most solvers stop here, certain the puzzle is misprinted.

The buried assumption is that the fastest person should always carry the torch. Question what the cost structure rewards instead: the 5 and the 10 are the expensive crossings, and in the greedy plan you pay for both separately. What if they crossed together, so the 10 absorbs the 5's cost entirely?

That requires staging: 1&2 across (2), 1 back (3), 5&10 across (13), 2 back (15) — the 2 was parked on the far side precisely so a cheap courier would be available — 1&2 across (17). Seventeen. You spent one extra cheap return (the 2's) to merge the two worst costs into a single bill. Verified optimal — no strategy beats 17 (the full strategy space has been searched; this is Dijkstra's algorithm territory, if you enjoy overkill).

The Move — Make the expensive items share a bill. Interrogate the greedy assumption by asking what the cost structure actually rewards — here, co-scheduling the two worst costs so one hides inside the other. Batch your slow database queries; schedule both disruptive migrations for the same maintenance window. (Provenance: traceable to Levmore & Cook's Super Strategies for Puzzles and Games, 1981; a famous 1990s Microsoft interview question, back when interviews were fun.)

The moves you now own

Six puzzles, six moves — the rigor shelf of the toolkit:

• Assume, then break it (2) — case analysis with contradiction as the executioner.
• Fold the lie onto itself (4) — route a signal through its own distortion so it cancels.
• Total wrongness is information (3) — a guaranteed error is worth a guaranteed truth.
• Anchor, then propagate (5) — absolutes first; never branch while a forced move remains; kill branches fast.
• Eliminate through others' knowledge (6) — declared ignorance is a filter; apply in dialogue order.
• Make the expensive items share a bill (7) — audit what the cost structure rewards before trusting greed.

A closing observation that the next chapters will keep sharpening. Nothing in this chapter required brilliance — the zebra fell to bookkeeping, Cheryl to three filters, the bridge to one distrusted assumption. Deduction is the most learnable of the thinking arts precisely because its whole content is procedure: exhaust the forced moves, name your assumptions, treat ignorance as evidence. Machines, it should be said, do this flavor of reasoning superbly — grids and schedules are their home turf. The reason to train it anyway arrives whenever a problem hands you constraints without handing you a solver: a contract, a diagnosis, a timetable, a witness who only tells you what they don't know.