Classic Logic Puzzles

What This Lesson Covers

Most interview logic puzzles yield to one of five moves: find an invariant; look at the extreme object, or count one thing two ways; count what a budget of trials can certify; change the frame; compute a different quantity.

1. Invariants and Parity

Statement. Let $Q$ be a function of the state. If every legal move preserves $Q$, then $Q$ is an invariant, $Q(\text{end})=Q(\text{start})$, and any target with a different value is unreachable; a strictly decreasing, bounded-below integer $Q$ (a monovariant) forces termination. Candidates: a count mod 2; a colouring (chessboard weights $\pm1$); a sum mod $m$; a product; a gcd. Sign flips are parity: meshed gears alternate, so the $k$-th gear in a chain turns as $(-1)^{k-1}$ relative to the first (closing the chain into a ring is Gear Train Parity).

Worked instances. Seven coins lie heads up; a move flips exactly two. All tails? The number of heads changes by $-2$, $0$ or $+2$, so its parity is invariant: odd at the start, even at the target. Colouring: a knight changes square colour every move, so a $5\times5$ board has no closed knight's tour (a closed tour has 25 moves, odd).

2. Extremal, Pigeonhole, Counting Two Ways, Optimality

Extremal principle. A finite nonempty set has a largest, smallest or most constrained element; extremality plus the local rule usually yields a contradiction.

Worked instance. Can every member of a finite set of reals be the average of two other members? Take the largest, $P$. Two other members are both smaller, so their average is smaller than $P$: impossible. An infinite set can (all integers).

Pigeonhole principle. $N$ objects in $n<N$ boxes: some box holds at least $\lceil N/n\rceil\ge2$.

Worked instance. Any $n+1$ numbers from $\{1,\dots,2n\}$ contain two coprime ones: the $n$ boxes $\{1,2\},\dots,\{2n-1,2n\}$ receive $n+1$ numbers, so one gets two consecutive integers, which are coprime.

Counting two ways. Summing the degrees of a graph counts each edge twice, so $\sum_v \deg v=2E$: four nodes of degree 3 and six of degree 2 give $(12+12)/2=12$ edges. So the sum is even, which alone settles some existence questions (Phone Connection, Segment Intersection).

Optimality: a bound and a construction. A maximum or minimum needs two halves: a bound (pigeonhole, an invariant, counting) and a configuration attaining it. Non-attacking rooks on an $8\times8$ board: two in one row attack, so at most 8; the diagonal attains it. Without a clean bound, use an exchange argument: if any configuration lacking a property can be improved locally, an optimum has it. Coins in stacks, product of sizes: splitting a stack of $s\ge5$ into $2$ and $s-2$ multiplies the product by $2(s-2)/s>1$, so no optimal stack exceeds 4; what remains is practice (Maximize Product).

3. Working Backwards and Search with a Budget

Working backwards. When the end is fixed, invert the moves from it. At each of three gates a traveller hands over half his apples plus one, and leaves with 1: he had $(1+1)\times2=4$ before the third gate, $(4+1)\times2=10$ before the second, $(10+1)\times2=22$ at the start. Integrality at each backward step often decides.

Search with a budget. Count how many cases $k$ trials can separate in the worst case, then build a strategy meeting it. Eggs: $n$ floors, unknown highest safe floor $T\in\{0,\dots,n\}$; a drop from above $T$ breaks the egg, otherwise it is reused. Let $f(k,e)$ be the most floors that $e$ eggs and $k$ drops can handle. One egg scans upward, $f(k,1)=k$. Otherwise drop as high as a break can still be recovered from: the floors below need $f(k-1,e-1)$, those above need $f(k-1,e)$, so

$f(k,e)=f(k-1,e-1)+f(k-1,e)+1,\qquad f(0,e)=0.$

Worked instance. Two eggs, 10 floors: $f(k,2)=k+f(k-1,2)$ gives $1,3,6,10$, so 4 drops: from 4, 7, 9, 10, scanning upward between the last two after a break. Summing the recursion for two eggs, and iterating it for three, is practice.

Elimination with limited comparisons. Picking the fastest few out of many with races of a fixed size is the same budget idea with a different ledger: a race certifies provable losses instead of floors. Lateral Thinking works it as selection by tournament; Horse Racing (25 horses, five lanes, top three) is its practice.

4. Symmetry and Relative Motion

Idea. Choose the frame in which the motion is simplest: in the water's frame, or one mover's, separations change at the velocity difference. Symmetry: a line through the centre of a centrally symmetric region halves its area, so a rectangular cake with a rectangular hole is halved by the cut through both centres.

Frame change. You row upstream at still-water speed $v$ against a current $c$; your hat falls in, you notice 10 minutes later and turn instantly. In the water's frame the hat is at rest and you moved away at $v$ for 10 minutes, so you return in 10 minutes, whatever $c$ and $v$ are (constant speeds).

Relative angular speed. The minute hand turns 6 degrees per minute, the hour hand 0.5. Each hand's angle is linear in the minutes $t$ past twelve, so set up the lead $5.5t$ and reduce it mod 360 (fold to at most 180 when the smaller angle is wanted). At 4:40 the minute hand is at $40\times6=240$ degrees, the hour hand at $280\times0.5=140$: 100 degrees apart.

5. Compute the Right Quantity

Idea. Identify the quantity the answer actually depends on, and compute that.

Circumference. $C=2\pi r$, so lengthening a loop by $\Delta C$ raises it by $\Delta r=\Delta C/(2\pi)$ all round; $r$ has dropped out. Lifting a belt 1 cm clear of a wheel everywhere needs $2\pi\approx6.28$ cm more belt.

Trailing zeros of $n!$. Each is a factor $10=2\times5$ and twos outnumber fives, so count factors of 5 among $1,\dots,n$: one per multiple of 5, a second per multiple of 25, a third per multiple of 125. For $30!$: six multiples of 5 plus a second five from 25, so 7 zeros.

Factorial versus exponential. Pair $k$ with $n+1-k$: $k(n+1-k)-n=(k-1)(n-k)\ge0$ for $1\le k\le n$, so $(n!)^2\ge n^n$ and $n!\ge n^{n/2}$; the same pairing bounds $n!$ from above (Factorial Vs Exponent). Against a fixed base $c$, each factor $k>c$ multiplies the ratio $n!/c^n$ by $k/c>1$, so $n!$ eventually wins; for $c=10$ the crossover is $n=25$. For two large powers, take logarithms or squeeze both between powers of a common base; for two logarithms, check monotonicity.

n! versus 10ⁿ on a log scale: 10ⁿ leads up to n = 24, n! from n = 25 on

Attacking an Unseen Puzzle

1. Restate with named variables: given, asked, assumptions (finite? integers? worst case or expectation?).
2. Find the invariant or the extreme. What does no move change? Which object is most constrained? For a maximum or minimum, hunt for the bound and the construction separately.
3. Try tiny cases, $n=1,2,3$, and tabulate; the pattern suggests the invariant, recursion or bound. Self-referential puzzles often yield to assuming exactly $k$ statements are true and checking each $k$ for consistency. Three cards say "exactly one of us is false", "exactly two", "all three": $k=0$ makes the third card true, $k\ge2$ has two true cards that contradict each other, so $k=1$ and only the second card is true.
4. Generalise and prove, then check against the tiny cases. Invariants prove impossibility, constructions possibility, counting bounds necessity, strategies sufficiency.

Interview insight. Name the method before the answer ("a parity invariant"). If stuck, announce the tiny-case plan and start it: interviewers grade process; a correct small table earns partial credit.

Practice

• Invariants and parity: Possible Cover (colouring; the method is taught in Lateral Thinking), The Locker Problem (parity of a count), Gear Train Parity, Last Ball, Plus One, Minus One, Grid Conversion, Three Pegs, Creating Zero, Final Number Possibilities.
• Extremal and pigeonhole: Pigeonhole Principle Application, Same Sum Subsets, Collinear Integer Points, Careful Soldiers, Consecutive Stocks.
• Counting two ways: Handshakes at a Party, Phone Connection, Segment Intersection, Gold Thief.
• Optimality (bound plus construction, or exchange): Max Fill, 5000 Sets, Maximize Product, Constrained Subsets IV, Largest Sum Subset, Min Collinearity, Polygon Constraints, Least N, Grid Paint I, Cutting Cube, Largest Mean Median Difference, Erase, Hungry Driver, Unequal Neighbors.
• Working backwards and budget search: 3 Bus Stops, Lily Pad, The Egg Drop Problem, 2 Eggs, 3 Eggs; Horse Racing (selection by tournament, taught in Lateral Thinking).
• Tiny cases and self-consistency: Truth.
• Symmetry and relative motion: Clock Angle, Hands Interchange, Meet Again, Boat And Steamer, Duck Escape, Treasure Island.
• Compute the right quantity: Factorial Vs Exponent, Strange Comparison I and II, Logarithm Comparison, Double Factorial, Painted Cube Faces, Watermelon Weight; warm-ups: Rope Around the Earth, Trailing Zeros in Factorial.
• Representation and encoding (a number's digits in a chosen base carry the information; taught with the weights in Weighing & Deduction): Chain Link, Polynomial Coefficient, Broken Calculator, Bacteria Population III, Fifth Card, Poisoned Wine I and II.
• Routed elsewhere: The Light Switch Room, The Burning Island, Toast Optimization, Bridge Crossing, 50 Wise Men to Lateral Thinking; Cheating Husbands to Games & Strategy; Drunk Passenger I to III, method taught in Probability Brainteasers. Same Temperature needs the intermediate value theorem, not taught in this path.