Twenty Questions, One Lie
The puzzle
I think of a number from 1 to 1,000,000. You ask yes-or-no questions. Without lying, twenty questions suffice.
Now suppose I am allowed to lie once. Roughly how many questions do you need, and why is the answer not forty?
Stuck?
One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.
Hint 1
Doubling every question would be the cost of asking everything twice. There is a cheaper way.
Hint 2
A lie is an error in a stream of bits. What do coding theorists do about those?
Show the answer Hide the answer
About 25 — twenty for the number plus roughly five for the error correction, not forty.
How to get there
Without lies, each question halves the candidates and twenty questions distinguish 2^20 = 1,048,576 numbers, comfortably more than a million.
A single lie turns the answers into a bit-string with at most one error - exactly the problem Hamming codes solve. Protecting 20 bits against one error needs about 5 extra bits, because 5 check bits can point to which of up to 25 positions is wrong, or report that none is.
So around 25 questions suffice, and Ulam's problem - this exact question - has the known answer 25 for a million. Asking everything twice would cost 40 and still not identify WHICH answer was the lie when a pair disagreed. Redundancy spread across all the questions is far cheaper than repetition.
The technique worth keeping
Treat a search under unreliable answers as a coding problem. The extra cost is the size of an error-correcting code, which grows like the logarithm of the message length rather than doubling it.