Twenty Questions, One Lie

  • Hard
  • Game strategy puzzles
  • Tests: Paying for error correction in questions

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.