Drew writes down a number between 1 and 1000. Mary must determine that number by asking "yes/no" questions of Drew. Mary knows that Drew always tells the truth. If Mary uses an optimal strategy, then she will determine the answer at the end of exactly how many questions in the worst case?

Question

Johanna Dickerson

Mathematics

13 November, 14:41

Drew writes down a number between 1 and 1000. Mary must determine that number by asking "yes/no" questions of Drew. Mary knows that Drew always tells the truth. If Mary uses an optimal strategy, then she will determine the answer at the end of exactly how many questions in the worst case?

+3

Answers (1)

Know the Answer?

Rene · Answer 1

Answer: 10 questions.

Step-by-step explanation:

The optimal aproach would be divide the total range in half, for example, she can ask:

Is the number equal or greater than 500?

if he answers no, now she knows that the numer is in the range 1 to 499

if he says yes, she can know that the number is in the range 500 to 1000.

Now, suppose that the answer is yes.

Now she can ask if the number is equal or greater than 750.

Now we have two possible sets. (500, 749) and (750, 1000).

Now we can divide those sets again, depending on the answer.

suppose we got the set of (750, 1000)

we can divide it into two sets and so on.

So, we have 999 options and we want to divide it by 2 until we reach to 1., the number of divisions by 2 is the number of times that she asked a question.

999/2^n ≤ 1.

we must find the smaller n that keeps the above inequality true.

999 ≤ 2^n

knowing that 2^10 = 1024.

999/1024 = 1024

So in the worst case, she should ask 10 questions.