Twenty Questions
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.