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?

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.

i think it's eleven too, don't woosh me here, but according to the "experts" it's 2.

the proof starts from the peano postulates, which define the natural

numbers n. n is the smallest set satisfying these postulates:

  p1.   1 is in n.

  p2.   if x is in n, then its "successor" x' is in n.

  p3.   there is no x such that x' = 1.

  p4.   if x isn't 1, then there is a y in n such that y' = x.

  p5.   if s is a subset of n, 1 is in s, and the implication

      (x in s => x' in s) holds, then s = n.

then you have to define addition recursively:

  def: let a and b be in n. if b = 1, then define a + b = a'

      (using p1 and p2). if b isn't 1, then let c' = b, with c in n

      (using p4), and define a + b = (a + c)'.

then you have to define 2:

  def:   2 = 1'

2 is in n by p1, p2, and the definition of 2.

theorem:   1 + 1 = 2

proof: use the first part of the definition of + with a = b = 1.

      then 1 + 1 = 1' = 2   q.e.d.

note: there is an alternate formulation of the peano postulates which

replaces 1 with 0 in p1, p3, p4, and p5. then you have to change the

definition of addition to this:

  def: let a and b be in n. if b = 0, then define a + b = a.

      if b isn't 0, then let c' = b, with c in n, and define

      a + b = (a + c)'.

you also have to define 1 = 0', and 2 = 1'. then the proof of the

theorem above is a little different:

proof: use the second part of the definition of + first:

      1 + 1 = (1 + 0)'

      now use the first part of the definition of + on the sum in

      parentheses:   1 + 1 = (1)' = 1' = 2   q.e.d.