Guess a number up to a million in twenty questions

Question

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

How many questions do you need to be certain of identifying the number? Prove that fewer questions cannot work, and describe the questions.

Accepted Answer

Twenty questions. Lower bound. A sequence of k yes-or-no answers can take 2 to the k different forms. To identify one of a million numbers with certainty, every number must produce a different answer sequence, so 2 to the k must be at least 1,000,000. Since 2 to the 19 = 524,288 is too small and 2 to the 20 = 1,048,576 is enough, at least 20 questions are needed. Achieving it. Ask "Is the number greater than 500,000?" and halve the remaining range each time: after each question the number of candidates is at most half of what it was, rounded up. Twenty halvings take a million candidates down …

Guess a number up to a million in twenty questions

Your answer

Discussion

Learn the concepts

Related questions