Here's another number guessing game:
I randomly pick a number from 1 to 1000. After you make your first guess at the number I will only tell you whether it is warmer (closer) or cooler (farther) or neither, to a 'zeroth guess' of 500.
For successive guesses I will tell your warmer, colder, neither, to the closest of the previous guesses.
What is the minimum number of guesses that would guarantee that you win with an optimal strategy?
What is this strategy?
Well, it is still sort of a binary search. I can use each guess to eliminate slightly more than half the possibilities. It is hard to improve on that.
At the start of the game it can be any number but 500, so there are 999 possibilities.
My first guess is 502.
If Jer says nothing, then I have won in 1 guess.
If Jer says "neither", then I know it is 501, and will win in 2 guesses.
If Jer says "warmer". then I know it is between 503 and 1000 (498 possibilities)
If Jer says "colder". then I know it is between 1 and 499 (499 possibilities).
From this point, my strategy is guess the extreme end of the range which is furthest from previous guesses. This always suffices to eliminate at least half of the remaining possibilities.
Let's assume the worst case, which is that is between 1 and 499.
I guess 1.
If Jer says nothing, then I have won in 2 guesses.
If Jer says "warmer". then I know it is between 2 and 250 (249 possibilities)
If Jer says "colder". then I know it is between 251 and 499 (249 possibilities)
Note that neither is not a possibility. (I might be able to reduce my expected number of guesses by guessing 2 instead of 1, but this will not reduce my worst case maximum, so for simplicity I am going to ignore that possibility).
If the range is between 2 and 250, then guess 250.
If the range is between 251 and 499, then guess 251.
At worst, my third guess will reduce the range from 249 to 124.
At worst, my 4th guess will reduce the range from 124 to 61.
At worst, my 5th guess will reduce the range from 61 to 30.
At worst, my 6th guess will reduce the range from 30 to 14.
At worst, my 7th guess will reduce the range from 14 to 6.
At worst, my 8th guess will reduce the range from 6 to 2.
At worst, my 9th guess will reduce the range from 2 to 1.
And my 10th guess is guaranteed to be enough.
Have I overestimated this method? Perhaps, but 10 is the answer I was expecting, so I'm not going to check further.
Edited on October 2, 2013, 8:05 pm
Am I getting warmer?
