Guess a number up to a million, but one answer along the way might be a lie
A friend picks a secret whole number between 1 and 1,000,000, and you may ask as many yes-or-no questions as you like to identify it. There's one catch: somewhere across the entire game exactly one of your friend's answers will be a lie, though you're never told which one. How few questions can you ask and still be guaranteed to pin down the number with total certainty?
Reveal the answer
Twenty-five questions are both necessary and sufficient — a tight bound worked out by Andrzej Pelc, versus roughly 20 for the same range with no lying allowed, so tolerating a single untruth costs only a handful of extra questions. Alfréd Rényi first posed the game in a 1961 paper that went largely unnoticed; Stanisław Ulam rediscovered and popularized it in his 1976 memoir.
— Alfréd Rényi; Stanisław Ulam, Ulam's game — Rényi, 1961 paper ("Napló az információelméletről"); Ulam, Adventures of a Mathematician, 1976
Go deeper: get the book →