Section 27.2

Deduction Puzzles

Reasoning from what others know (Cheryl's birthday), mislabelled boxes, decoding rules from examples, trick questions (fenceposts, a snail in a well), Hilbert's hotel.

Toolkit

These puzzles hinge on translating ordinary words — “knows”, “between”, “mixed up”, “labelled wrong” — into precise logical or arithmetic constraints, then eliminating possibilities systematically rather than simulating the story literally.

Key tools:

Counting care: $n$ events in a sequence give $n-1$ gaps; a final push to a goal need not be matched by a trailing setback.
Epistemic statements: “X does not know $v$ ” eliminates values of $v$ that would make $X$ ’s private information determine it; “X now knows $v$ ” means exactly one candidate survives after prior eliminations. Apply statements in the order given, each pruning the surviving set.
Adversarial labelling: if every label is guaranteed false, the one sample that disambiguates the most (e.g. the bag called “mixed”) pins down the whole assignment by exclusion.
Decoding: find the simplest rule (e.g. a bit per independent attribute) consistent with all given examples simultaneously, not just one.
Bijective infinities: Hilbert’s Hotel results, for a countable set $S$ :
$\mathbb{N}\cong \mathbb{N}+1 \cong 2\mathbb{N} \cong \mathbb{N}\times\mathbb{N} \cong \mathbb{N}\cup \mathbb{N}\cup\cdots$
via explicit shift, doubling, or pairing maps.

Problems