06 · Logic Puzzles
Universal method for truth-teller / liar puzzles
Let = “A is a knight (truth-teller)“. Then whatever A says, call it : A knight’s statement is true; a knave’s statement is false. Case-split on each person’s type and kill contradictions.
Puzzle #1 — Knights & Knaves
Knights always tell the truth, knaves always lie. p = A is a knight, q = B is a knight.
(a) A: “B is a knight.” B: “The two of us are opposite types.”
B’s statement = = .
| Case | Check | Result |
|---|---|---|
| A knight (p=T) | A’s claim ⇒ q=T. B (knight) says p⊕q = T⊕T = F — a knight lying ❌ | impossible |
| A knave (p=F) | A’s claim false ⇒ q=F. B (knave) says p⊕q = F⊕F = F — a knave saying a falsehood ✅ | consistent |
Answer: both A and B are knaves.
A’s statement is “B is a knight”, which in symbols is just q.
The rule for these puzzles is that a speaker is a knight exactly when what they say is true:
The note wrote out B’s statement as a formula but skipped A’s. Putting both side by side:
| Speaker | Statement (English) | Statement (logic) | Constraint |
|---|---|---|---|
| A | ”B is a knight” | ||
| B | ”We are opposite types” |
Solving it:
- From A’s constraint, , so p and q have the same value. A and B are the same type.
- Since they’re the same type, is F, so B’s statement is false.
- B’s constraint is , so q = F, meaning B is a knave.
- Since p = q, p = F, meaning A is a knave.
Both are knaves. As a check, A (a knave) says “B is a knight”, which is false. B (a knave) says “we’re opposite”, which is false because they’re the same type. Both are lying, as knaves must.
This is the same answer as the case table, but writing each person’s statement as a formula and attaching speaker ↔ statement lets you solve without guessing cases. That helps on harder puzzles.
(b) A: “At least one of us is a knave.” B says nothing.
If A were a knave, “at least one knave” would be true (A is one) — a knave can’t say something true ❌. So A is a knight ⇒ statement true ⇒ B must be the knave. A knight, B knave.
🏠 Homework — solved
(c) A: "The two of us are both knights." B: "A is a knave."
- A knight ⇒ both knights ⇒ B knight ⇒ B’s “A is a knave” is false — a knight lying ❌
- A knave ⇒ “both knights” is false ✅ ⇒ B’s “A is a knave” is true ⇒ B is a knight ✅
A knave, B knight.
(d) A: "I am a knave or B is a knight." B says nothing.
- A knave ⇒ “I am a knave ∨ …” is true — a knave can’t say that ❌
- So A knight ⇒ statement true; “I am a knave” is false ⇒ “B is a knight” must be true.
A knight, B knight.
(e) Both A and B say "I am a knight."
A knight saying “I’m a knight” — true ✅. A knave saying “I’m a knight” — false ✅. Every combination is consistent.
Cannot be determined (all four combinations possible). ⚠️ Edge case: “I am a knight” carries zero information.
Puzzle #2 — The detective & four witnesses
- If the butler tells the truth, so does the cook →
- The cook and the gardener cannot both tell the truth →
- The gardener and handyman are not both lying →
- If the handyman tells the truth, the cook is lying →
Solve:
- Try c = T: then (2) ⇒ g = F, (3) ⇒ h = T, (4) = F ❌. So c = F.
- c = F with (1): ⇒ b = F.
- (2) and (4) now hold automatically. Only (3) remains: (g, h) ∈ {(F,T), (T,T), (T,F)}.
🎯 Trick · Assume the Most Frequent Variable
The idea in one line
Fix the variable that touches the most clues: one guess then simplifies the most clues at once.
Why it works
Each clue is a small rule connecting a few variables. When you give one variable a value:
- every clue containing it becomes simpler
- often a clue is left with one unknown, which is now forced
- that forced value simplifies more clues → chain reaction
More clues touched → more forced values → you reach the answer (or a contradiction) faster.
🧩 Like Sudoku: start with the cell that has the most constraints around it.
Detective puzzle · Count the occurrences
Variable Appears in Count c (1), (2), (4) 3 ⭐ g (2), (3) 2 h (3), (4) 2 b (1) 1 → Assume c first.
What goes wrong if you guess b first
Guess b = T (b is in only 1 clue):
- (1) →
- (2) → , (3) → , (4) → ❌
So b = F. But then:
- (1) is always true → you learn nothing about c
- 3 unknowns left → you must guess again (and maybe again)
Starting with a variable that’s in few clues tends to cost extra guesses.
Guess c first · Done in one step
Assume c = T:
- (2) → g = F
- (3) → h = T
- (4) → ❌
∴ c = F → (1) forces b = F → only remains. One assumption, finished.
Bonus · Which value to try first
Try the value that activates the clues:
Clue type Try this Why Implication true left side forces the right side false left side makes the clue automatically true, so no info OR makes your literal false, so the other literal is forced That’s why c = T was the right first try: (2) forced g → (3) forced h → clash with (4).
Quick recipe
- Count how many clues each variable appears in.
- Pick the highest count (tie → the one in the shortest clues).
- Try the value that forces others, not the one that makes clues automatically true.
- Contradiction? The opposite value is correct, and half the possibilities are gone.
Caveat
This is a shortcut that usually works, not a guarantee: it doesn’t always give the minimum number of steps. For GATE-sized puzzles (3–5 people) it almost always works with one assumption.
Answer
The butler and cook are lying. We can’t determine the gardener and handyman individually — only that at least one of them is telling the truth.
Solved Problem — GATE 2015 (Set 3), 1 mark
Type 1 always tell truth, Type 2 always lie. A person tosses a coin and says: “The result is head if and only if I am telling the truth.” (a) head (b) tail (c) if Type 2 then tail (d) if Type 1 then tail
Let p = result is head, q = speaker tells the truth. Statement .
- Type 1 (q = T, S must be T): = T ⇒ p = T → head
- Type 2 (q = F, S must be F): = F ⇒ p = T → head
Answer: (a) — head, either way.
Shortcut
A statement of the form “X iff I’m telling the truth” always forces X = TRUE, whoever says it. Since .
Prev ← 05 Translation and Consistency · Next → 07 Tautology Contradiction Satisfiability