wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> "Moving" Binary Search Riddle
        
(Message started by: k2xl on Sep 16^th, 2011, 11:35am)

Title: "Moving" Binary Search Riddle
Post by k2xl on Sep 16^th, 2011, 11:35am

I've been a reader of these forums for years... haven't posted since 2008, but wanted to share this riddle.

I was playing a game with someone where she would have to guess what time it was without looking at the clock behind her (I could see the clock). Every time she guessed incorrectly I would tell her if it was earlier or later.

This got me thinking of an interesting riddle (I don't know the answer to this, but maybe someone could figure it out?)

Most of us are probably familiar with binary search and it having big O notation of log (base 2) (x) .

Was curious... what if I proposed the following scenario:

Danny thinks of a random number between 0 and 100 (he picks p between x and y). Kelly has to guess the number. If she guesses incorrectly, Danny tells her if the number is higher or lower and increments the number "p" in his head by 1 (let's call this value k). Danny will not increment "p" by "k" if x > "p+k" > y

What's the optimal strategy for Kelly to pick "p" when x = 0, y = 100, and k = 1

And is there a general solution to this problem? (i.e. let's say k was negative) ?

Again I have absolutely no idea how to solve this, but I thought it could be interesting because it reminded me of guessing the time since a past guess could be correct later on.

Title: Re: "Moving" Binary Search Riddle
Post by towr on Sep 16^th, 2011, 1:02pm

I'm not sure I understand the problem entirely. Does Danny always increase p when Kelly makes a wrong guess? If so she could just add k to her search-range.
(If she knows p is between A and B, and guesses (A+B)/2, then the next step she will know the new p is between A+1 and (A+B)/2+1 or between (A+B)/2+1 en B+1)
Or she could just try to find the original p, but add n*k to her guess, where n is the number of times she guessed wrong.

Title: Re: "Moving" Binary Search Riddle
Post by Hippo on Sep 16^th, 2011, 4:27pm

And if both x and k are unknown it is a variant of submarine hunting problem.