I’m thinking of a whole number between 1 and 1,000. You will ask me yes-or-no questions until you figure it out.
How many questions do you need to guarantee that you pinpoint the number? (Announcing your final guess does not count as a question.)
What if you must submit your questions in advance? In other words, we won’t have an interactive conversation. You will write down all of your questions, then I will answer them all as a batch, and then you will guess the number. I might answer them in any order (e.g., I might answer the seventh question first), so a later question cannot depend on the answer to an earlier one.
The optional hint tells you the numeric answers but leaves it to you to figure out the method.
Amazingly, both scenarios require the same number of questions: 10.
Amazingly, both scenarios require the same number of questions: 10. The natural solution to part one is called binary search. You first ask, “Is the number greater than 500?” Then, no matter what I answer, you’ve cut the number of possibilities in half. Each of your subsequent questions can cut the remaining number of possibilities in half, too. If I say my number is greater than 500, then your second question should ask if it’s greater than 750; if I say my number is less than or equal to 500, then your second question should ask if it’s greater than 250. There are 1,000 possibilities at the beginning, then 500 after one question, then 250 after two questions, and so on. Cutting 1,000 in half 10 times leaves you with only one possibility, implying you’ve found the answer. In general, n questions suffice to pinpoint a number between 1 and 2n(and because 210 = 1,024, 10 questions suffice for 1 to 1,000).
At first, it seems like removing the interactivity would require more questions, but it doesn’t. One way to solve part two is to imagine my number written in binary. A number between 1 and 1,000 can be represented with 10 binary digits (the largest 10-digit binary number would be 10 1’s, 1111111111, which equals 1,023). So you can ask directly about the number itself. You start with “Is the first digit of your number in binary a 1?” If I say no, then you know the first digit of the binary representation is a 0. Then you can proceed to ask, “Is the second digit of your number in binary a 1?” After 10 questions, I will have described a specific 10-digit binary number, which maps to a unique integer.
We’d love to hear from you! E-mail us at games@sciam.com to share your experience.