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

Home > General
Interval Guessing (Posted on 2019-10-21) Difficulty: 2 of 5
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.)
Solution solution | Comment 1 of 10
The same sort of binary splitting would work in this guessing game as in the game where the guesser specifies one number and is told if it's too high or too low. Either way, the number of possibilities approximately halves in each turn.

In the one-number higher-lower game it's ambiguous when the remaining range is even, and it doesn't really matter whether you choose, say, 5 or 6 in a range of 1 to 10.

Similarly in the current case, the ambiguity arises when an odd number is in the range, such as the presented 1 - 15. You could choose initially, 1-7 or 1-8. (or likewise the complementary 8-15 or 9-15).

Asking, say 1-7, will either narrow the range to 1-7 or to 8-15. Say its the wider 8-15: then guess 8-11; if that gets a no then you know it's 12-15 and you can guess 12-13.

The expected number of guesses will be one or two above that for the higher/lower version, but no more, and it will be the best you can do.

  Posted by Charlie on 2019-10-21 21:16:51
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (5)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2021 by Animus Pactum Consulting. All rights reserved. Privacy Information