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 'zero^th 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?

My comment was a 'Thought' not an answer, Jer!

Here is a primitive method that guarantees a solution in no more that 16 steps:

Say I choose 2^8 as my first guess. If it is 'cooler' I then choose 2^9+2^8, 2^8+2^7, 2^9+2^8-2^7, etc. closing in on the 'pole' of 500 until I receive a 'warmer' result.

If and when I get a 'warmer' result, this becomes the new pole of the search, and I again successively subtract and add decreasing powers of 2 from that until I get another warmer result.

And so on until

(1) The next number to be added or subtracted is 0, in which case I am done; or
(2) I get a 'neither' result which provides the solution at once.

But 16 steps suggests that only 1/3 of the remaining possibilities are eliminated each turn -  I'd be dumbfounded if that figure couldn't be bettered. As you note, 1000*(1/2)^n=1 implies that n is around 10.

Edited on October 2, 2013, 3:49 am

Posted by broll on 2013-10-02 02:31:18