Twenty Questions

  • Easy
  • Game strategy puzzles
  • Tests: Halving the candidates every question

The puzzle

I am thinking of a whole number between 1 and 1,000,000. You may ask yes-or-no questions and I must answer truthfully.

How many questions do you need in the worst case?

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

Each answer can at best halve the set of numbers still possible.

Hint 2

How many halvings take a million down to one?

Show the answer Hide the answer

Twenty.

How to get there

Each yes-or-no answer distinguishes at most 2 cases, so n questions distinguish at most 2^n. You need 2^n at least 1,000,000.

2^19 = 524,288, which is not enough; 2^20 = 1,048,576, which is.

And twenty suffices in practice: ask "is it above the midpoint?" each time, which halves the range exactly and always leaves one candidate after twenty.

The technique worth keeping

Count the information first, then find a question that actually achieves the bound. Halving is the question that does, which is why binary search appears everywhere this bound does.