All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 My favorite number (Posted on 2003-06-16)
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.

 See The Solution Submitted by Jon Rating: 2.6667 (6 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Solution Comment 15 of 15 |

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

 Search: Search body:
Forums (0)