All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Interval Guessing (Posted on 2019-10-21)
I am thinking of an integer in the interval [1-15]. You are to try to guess it by telling me intervals and I will tell you if my number lies in that interval.

For example if my number is 6 and you guess [6-9] I will tell yes but if you guess [7-11] I will tell you no but not if my number is higher or lower.

You win by guessing an interval of just one number and that number is my number. Find a strategy that minimizes the expected number of guesses.

 No Solution Yet Submitted by Brian Smith Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 some thoughts | Comment 2 of 10 |
I am wondering if there is perhaps some subtlety being missed here by assuming that the binary search is always optimal... In fact, in the literature, it is often stated it becomes non-optimal for small arrays.

As an extreme example, say instead of 15, the array has N=3 elements. I.e, the choices are 1, 2, or 3. It is simple to show the interval guessing of {1}, then {2}, then {3} is a better strategy than first guessing {2,3}.

The first way has an expectation of 2 guesses while the second way has 2.333...

So, some thought must go into the exact answer, such as the  details of the endgame.

In fact, there is at least one paper that claims that the "quadratic search" (a quartile search) for small N is better (less steps) than the binary search, but sadly the paper is almost unreadable due to language difficulties.

Edited on October 23, 2019, 8:29 am
 Posted by Steven Lord on 2019-10-23 03:56:26

 Search: Search body:
Forums (1)
Random Problem
Site Statistics
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox: