Renyi-Ulam: Twenty Questions With a Liar, Explained

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.

Each tolerated lie costs roughly an extra $\log_2 N$ questions worth of redundancy, so finding one number among a million candidates ( $\log_2(10^6) \approx 20$ questions with a truthful answerer) can require noticeably more than 20 questions once even a single lie is allowed, since some of those questions must go toward catching the lie rather than narrowing the search.

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.

Renyi-Ulam: Twenty Questions With a Liar

Related concepts

Practice in interviews

Further reading