A teacher thinks of a number between 1 and 15 and three students guess, each time being told "high" or...

logic/guess.the.number New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

A teacher thinks of a number between 1 and 15 and three students guess,
each time being told "high" or "low"; from what the teacher says, what
should the fourth student guess?

Teacher: I'm thinking of a number between 1 and 15.  You will take
         turns guessing the number; if your guess is incorrect, I'll
         tell you if you were high or low.  Your object, as a group,
         is to find the number in the fewest possible turns.
Student 1: 1.
Teacher: That's low.  Don't feel too bad; even using the most efficient
         procedure it would have taken the maximum number of turns.
Student 2: 15.
Teacher: That's high.  Don't feel too bad; even using the most efficient
         procedure it would have taken the maximum number of turns.
Student 3: 8.
Teacher: That's low.

You are Student 4.  What's your best guess?

(This may be too easy for this group.  On the other hand, if people
are still posting the polar bear puzzle.....!  Besides, it held up my
brother-in-law for a while, and he's pretty sharp.)

-- Pete Kimball <U31850@uicvm.uic.edu>

[ Editor: the opening sentence is the editor's summary; the original
puzzle follows it. ]

Show solution

If the most efficient search method (binary) would have taken a maximum
number of guesses at the start, then we know that the answer is
1,3,5,7,9,11,13, or 15.  After the first guess we know it is not 1.
The second student was also told that a binary search would require a
maximum of guesses, so we know the answer is 3,7,11, or 15.  The second
student eliminated 15.  The third student's guess shows us that the
answer must be 11.

-- Dan Bergmann <dbergmann@llnl.gov>