Author |
Topic: "Moving" Binary Search Riddle (Read 4221 times) |
|
k2xl
Newbie
  
Posts: 17
|
 |
"Moving" Binary Search Riddle
« on: Sep 16th, 2011, 11:35am » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: "Moving" Binary Search Riddle
« Reply #1 on: Sep 16th, 2011, 1:02pm » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: "Moving" Binary Search Riddle
« Reply #2 on: Sep 16th, 2011, 4:27pm » |
Quote Modify
|
And if both x and k are unknown it is a variant of submarine hunting problem.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print