Brainteasers & Logic
Logic Puzzles (Hats, Weighing, Liars)
Overview
Logic puzzles test structured deductive reasoning under constraints. The key strategy: work backwards from what the LAST actor knows, or enumerate the information states explicitly. For hat problems: each person's strategy maps their observations to an action. For weighing: each weighing gives 3 outcomes, so n weighings can distinguish 3^n objects. The interview tests whether you can think systematically rather than randomly.
How to Recognize
- โPerfect logical agents who know everyone else is logical
- โ'N prisoners, see everyone else's hat but not their own'
- โWeighing problems with a balance scale
- โKnights and knaves (liars and truth-tellers)
Step-by-Step Approach
- 1.Work backwards: what does the LAST person know? What can the FIRST deduce?
- 2.Use induction: solve n=1 case, then n=2, then generalize
- 3.Identify what information each agent can deduce from the situation itself
- 4.Each weighing partitions into 3 groups (balance scale: left heavy, balanced, right heavy)
Key Formulas
Worked Examples
Problem
100 prisoners each wear a red or blue hat. In a line, each can see everyone in front. Starting from the back, each says 'red' or 'blue'. Guards execute anyone who's wrong. Strategy to save at least 99?
Solution
The last prisoner (sees all 99 others) uses their guess to communicate information to everyone else.
Strategy: last prisoner counts the number of red hats they see. If odd, say 'red'. If even, say 'blue'.
Now prisoner 99 knows: (a) parity announced by prisoner 100, (b) how many red hats they see in front. They can deduce their own hat.
Prisoner 99: if parity was 'odd' (meaning total reds in positions 1โ99 is odd) and they see even reds, their hat must be red. Continue this logic.
Every prisoner from 99 down to 1 can deduce their hat color with certainty.
Prisoner 100 has 50/50 chance (first to guess). Expected: 99.5 prisoners saved.
Answer
Parity strategy saves all but the last prisoner (50/50). The key: encode the global parity information in the first guess, then everyone deduces from the parity + what they see.
Common Mistakes
- !
Trying to solve the 12-ball problem by trial and error instead of systematic information counting.
- !
In hat puzzles, forgetting that each prisoner's DECISION (not just their guess) is visible to those behind them.
- !
Not thinking about what information each weighing gives: balance = fake not in these 8, left-heavy = fake is in left OR right (depending on setup).
Practice Problems
Click "Show Answer" to revealA bat and ball cost 1.00 more than the ball. How much does the ball cost?
Three gods: Truth (always true), Lie (always lies), Random (random). You can ask 3 yes/no questions to identify each. How?