Renyi-Ulam: Twenty Questions With a Liar

Ordinary twenty questions is a clean information-theory exercise: with a truthful answerer, $\log_2 N$ yes-or-no questions pin down any one of $N$ possibilities, because each honest answer halves the remaining candidates. The Renyi-Ulam problem asks a harder version: what if the answerer is allowed to lie up to $e$ times, and you don't know in advance which answers (if any) were lies?

A single potential lie means a "yes" answer can no longer eliminate half the candidates outright, because that answer itself might later turn out to have been false. The questioner needs extra questions purely as redundancy, enough repeated or cross-checking questions that any one lie gets caught out by contradicting the others, without knowing beforehand which answer to distrust.

The problem is a favorite in interviews precisely because the naive instinct, "just ask the same question twice to catch a lie", is close but not quite optimal; the actual optimal strategies use a more clever encoding related to error-correcting codes, tracking a running score across multiple candidate answers rather than re-asking single questions. It's a useful reminder that redundancy against noise, whether in a guessing game or a noisy data feed, has a real, quantifiable cost.