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.

You can find the number with six guesses.

Let us work backwards; given a certain number of guesses, determine the maximum range of numbers from which you can determine a single number.

If you have one guess, then you of course know what the answer is without having guessed at all. However, you will still require one guess to guess the correct answer.

|1|

With two guesses, you can find the answer out of three numbers. Guess the middle value, and either you have guessed correctly, or the answer is the higher or lower value, in which case you must use the second guess to find the correct answer.

1 |2| 3

Here's where it gets tricky.

In order to ever find the number, it is therefore necessary to have no more than three numbers to choose from when you get down to your last two guesses.
If you have seven numbers with three guesses, and you guess the middle value, then either you are correct, or the answer is either in the higher three or the lower three, in which case you can determine it from the final two guesses.

1 2 3 |4| 5 6 7

Similarly, with four guesses, you must narrow it down to no more than seven possibliities with the first guess, so if you guess the middle value out of 15 numbers, you have either guessed correctly or eliminated all but 7 of the choices.

1 2 3 4 5 6 7 |8| 9 10 11 12 13 14 15

In general, a single guess with x choices will narrow it down to at most (x-1)/2 possibile values for the next guess. With n guesses, you can narrow it down to (and guess) a single number out of 2^n-1 possiblities by guessing the median value each time.

However, the problem does not require that you may guess only a single value. Rather, it says that you may guess "anything you like," and will be answered with whether (or not) the number in question is "higher or lower then (sic) your guess."
Given that, it is possible to guess a range of values instead of a single value.

With one or two guesses, the range you would guess is a single value anyway, and the number of choices you can narrow down are the same.

Recall that with three guesses, your first guess must narrow the field down to no more than three values.
If, then, you guess a range of three values, with three higher and three lower numbers, you can be assured of being able to narrow down your last two guesses.

1 2 3 |4 5 6| 7 8 9

Therefore, you can find a single number out of 9 values (instead of 7) by guessing the range.

In general, a guess of the middle range of x values will narrow it down to x/3 possibilities for the next guess, instead of (x-1)/2, and actually the operation is ternary instead of binary.
With n+1 guesses (since the last guess is always needed for the actual number, even after you have narrowed it down), you will in this manner be able to find a single number out of 3^n possibilites.

If you have five guesses, you can find the answer out of 3^4=81 possible values.
This is not enough, but with six guesses, you can find and guess a single value out of 3^5=243 numbers.
Therefore, to find a number out of the 100 values between 1 and 100, you need six guesses.

..
My first guess would be "82 to 90."

If it is correct, then you have only 9 values to deal with and will find the number in three more guesses for a total of four (or possibly three).
If the answer is higher, then you have 10 values from 91 to 100, and will find the number in at most four more guesses, but it would be possible to do it in two or three more.
If the answer is lower, then you have 81 values, so it will five more guesses (four if the number is one less than a multiple of three), for a total of six.
My reasoning behind that is, at least it's easy math when you have 81 values.

Posted by DJ on 2003-06-17 17:24:10