Section 27.1

Truth-Tellers and Liars

Knights and knaves, finding a truth-teller among liars, self-referential statements.

Toolkit

Knights always tell the truth, knaves always lie; the key technique is to analyse statements for logical self-consistency rather than trust content. A statement’s truth value must satisfy any equation it imposes on itself (fixed-point reasoning): if a statement of the form “exactly $k$ of these $n$ statements are true” is asserted, let $T$ be the true count and check which $k$ make the assertion “statement says $k$ ” consistent with being true or false, i.e.

\text{statement $i$ true} \iff (\text{claim}_i = T).

For composite questions, route through a double negation: asking “what would X say about Y?” flips a lie twice, so the reported answer is always the truthful one, allowing a single question to identify status regardless of who answers. For majority-honest populations, pairwise mutual testimony lets you prune greedily: any disagreeing pair can be discarded since at least one must be lying, preserving the honest majority until one or two agents survive uneliminated.

Problems