In the book Hard Drive: Bill Gates and the Making of the Microsoft
Empire, by James Wallace and Jim Erickson, on page 261 (Chapter 5,
Growing Pains) there is the following paragraph:

... Friedman was able to handle MacGregor’s first tough question, the
high-low number puzzle. This a game theory question in which the
candidate has to guess a number from 1 to 100 that the interviewer has
selected. The candidate is told if the guess is high or low and
continues until guessing the correct number. There is a mathematical
strategy for getting the number in the fewest possible guesses, which
is about seven.

What is the mathematical strategy, and how does it work?

Hi Markabe,

  Good day. There is a very simple approach to this problem. In fact,
this involves a technique similar to binary searching. You have to
find out initially in which half it is. If it is in the top half,
you'll have to find out in which half it is, in that half.

Take for example :

Assume the person is thinking of 37.

1. Guess = 50. Guess > Answer. Hence it is in the top half. Next guess
is the middle term of the previous half.
2. Guess = 25. Guess < Answer. Lower half.
3. Guess = 37 (ans) or 38 (assuming this). Guess > Answer. Upper half
4. Guess = 32. Guess < Answer. Lower Half
5. Guess = 35. Guess < Answer. Lower Half
6. Guess = 37. Answer got!

The maximum number of steps taken using this method is 7.

Its basically 2 to the power of n (2^n), where 2^n > number of terms,
and 2^(n-1)< number of terms.

If there are 500 terms, then
2^9 = 512
2^8 = 256

Number of steps = 9.

For more information on binary searchm you can visit the following URL
http://www.cs.adfa.oz.au/teaching/studinfo/ada/Searching/binary_search.html

Have a good day.

Cheers,
aditya2k.

Search Terms
Binary Search -tree

Perfectly clear now; I also liked cheef-ga's explanations. Well done to both of you!

The strategy is simple.

Begin with a value of 1 as your LOWEST possible number.
Begin with a value of 100 as your HIGHEST POSSIBLE number.

1)  Make your guess the number halfway between the LOWEST POSSIBLE and
HIGHEST POSSIBLE NUMBER.  (Round off to the nearest whole number.  For
example, your very first guess would be 50.)
2)  If you are told your guess is too low, your guess is now your new
LOWEST POSSIBLE NUMBER.  If you are told your guess is too high, your
guess is now your new HIGHEST POSSIBLE NUMBER.
3)  Repeat steps 1 & 2 until you arrive at your result.

This works because each time you guess you eliminate half of all
possible answers, and 2^8 = 128, more than the number of choices you
have.

A slightly clearer way of answering "Why does it work?" is to say that
if you start with 100 and keep dividing by 2, you can only do it 7
times.

the number of remaining answers is halved each time:
100 / 2 = 50
50 / 2 = 25
25 / 2 = 12.5 (rounded to 13)
13 / 2 = 6.5 (rounded to 7)
7 / 2 = 3.5 (rounded to 4)
4 / 2 = 2
2 / 2 = 1
That's all

Actually, markabe, there is an even faster method of guessing a number
between 1-100. I've played this game a lot during college. First you
take the square root of pi,  divided by the accelerated rotation of
the earth, throw in the velocity constant, times the Hubble effect and
you usually get the number "12". :) PS--- for you kids reading this at
home, don't try it, you can completely erase the hard drive if you put
this through a Windows platform.