You are trying to guess my favorite number. I tell you it is from 1-100 somewhere and is an interger. You can guess anything you like and I will tell you whether my number is higher or lower then your guess. What is the smallest number of guesses you can make to make sure you will get my number, no matter what it is?

Assume that I don't lie to you about the greater or less than value.

Given the usual caveats about it being a genuinely random number with each of the values 1,2,...100 having equal chance (1%), then the answer is 7 using the methodology of halving the valid range.

With each guess the best one can hope to achieve is to halve the range of valid numbers, so the first guess is always 50 - after which the worst case is that there are 50 possibilities (ie the number is in the range 51-100). After the second guess there are at most 25 possibilities. Etc, etc until the seventh guess when the range is only 1 number.

As an aside, using this methodology seven guesses can pick a number from up to 127 options.

Posted by fwaff on 2003-06-16 03:09:46