Guess my number from 1 to 1000 in ten questions

Question

I think of a whole number from 1 to 1000 and keep it secret. You may ask me questions I can only answer yes or no. What is the smallest number of questions that guarantees you can always pin down my number?

Accepted Answer

Ten questions always suffice, and fewer cannot be guaranteed. Each yes/no answer is one bit. A question with only two possible answers can, at best, cut the set of remaining candidates in half. Start with 1000 possibilities. After each well-chosen question the count at most halves, so after q questions you can distinguish at most 2^q different numbers. Find the needed q. You need 2^q \ge 1000. Since 2^9 = 512 < 1000 and 2^{10} = 1024 \ge 1000, you need 10 questions. Nine questions can separate only 512 cases, so some pair of numbers would give identical answers and stay indistinguishable, 9 i…

Guess my number from 1 to 1000 in ten questions

Your answer

More Brainteasers questions