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.

6 or 7, depending upon Jon's veracity.

If Jon also does not lie to us about the value of the number equal to our guess, using the technique of making our guess the floor (|x]) of the average of the lowest and greatest possible integers, one can find the value in 6 guesses.

For example, say Jon's favorite number is 17.

1st guess: 50 = |( 1 + 100) / 2]  --- "LOWER"
2nd guess: 25 = |( 1 +  49) / 2]  --- "LOWER"
3rd guess: 12 = |( 1 +  24) / 2]  --- "HIGHER"
4th guess: 18 = |(13 +  24) / 2]  --- "LOWER"
5th guess: 15 = |(13 +  17) / 2]  --- "HIGHER"
6th guess: 16 = |(16 +  17) / 2]  --- "HIGHER"
At this point it is no longer a guess, we know Jon's favorite number is 17.

If, on the otherhand, Jon can lie about the value equal to our guess, the number "guessed" should be the non-integer average, with any integer "guessed" included in the range of possible numbers. For this example, say Jon's favorite number is 19.

1st guess: 50.5 = |( 1 + 100) / 2]  --- "LOWER"
2nd guess: 25.5 = |( 1 +  50) / 2]  --- "LOWER"
3rd guess: 13   = |( 1 +  25) / 2]  --- "HIGHER"
4th guess: 19   = |(13 +  25) / 2]  --- "LOWER" (a lie)
5th guess: 16   = |(13 +  19) / 2]  --- "HIGHER"
6th guess: 17.5 = |(16 +  19) / 2]  --- "HIGHER"
7th guess: 18.5 = |(18 +  19) / 2]  --- "HIGHER"
At this point it is no longer a guess, we know Jon's favorite number is 19.

Edited on June 17, 2008, 8:45 am

Posted by Dej Mar on 2008-06-17 04:59:10