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.)
Some Thoughts correction to previous post | Comment 9 of 10 |
(In reply to re(2): Full solution: 15 and beyond by Charlie)

My previous post, in response to Steven Lord's request for strategy when you only need to find which is the chosen number, rather than need to place a formal guess for it, was flawed in that the initialization of the expected value for n=1 should have been zero rather than 1. The correct table, this time for the first 100 values of n, follows (showing that in fact the binary method does always still work, as one of the optimal choices):


  n exp. guesses optimal first choice
                         (only the smaller one is shown
                          -- also subtract from n as the larger choice)
  3 1.666667     1
  4 2.000000     2
  5 2.400000     2
  6 2.666667     2  3
  7 2.857143     3
  8 3.000000     4
  9 3.222222     4
 10 3.400000     4  5
 11 3.545455     4  5
 12 3.666667     4  5  6
 13 3.769231     5  6
 14 3.857143     6  7
 15 3.933333     7
 16 4.000000     8
 17 4.117647     8
 18 4.222222     8  9
 19 4.315789     8  9
 20 4.400000     8  9 10
 21 4.476190     8  9 10
 22 4.545455     8  9 10 11
 23 4.608696     8  9 10 11
 24 4.666667     8  9 10 11 12
 25 4.720000     9 10 11 12
 26 4.769231    10 11 12 13
 27 4.814815    11 12 13
 28 4.857143    12 13 14
 29 4.896552    13 14
 30 4.933333    14 15
 31 4.967742    15
 32 5.000000    16
 33 5.060606    16
 34 5.117647    16 17
 35 5.171429    16 17
 36 5.222222    16 17 18
 37 5.270270    16 17 18
 38 5.315789    16 17 18 19
 39 5.358974    16 17 18 19
 40 5.400000    16 17 18 19 20
 41 5.439024    16 17 18 19 20
 42 5.476190    16 17 18 19 20 21
 43 5.511628    16 17 18 19 20 21
 44 5.545455    16 17 18 19 20 21 22
 45 5.577778    16 17 18 19 20 21 22
 46 5.608696    16 17 18 19 20 21 22 23
 47 5.638298    16 17 18 19 20 21 22 23
 48 5.666667    16 17 18 19 20 21 22 23 24
 49 5.693878    17 18 19 20 21 22 23 24
 50 5.720000    18 19 20 21 22 23 24 25
 51 5.745098    19 20 21 22 23 24 25
 52 5.769231    20 21 22 23 24 25 26
 53 5.792453    21 22 23 24 25 26
 54 5.814815    22 23 24 25 26 27
 55 5.836364    23 24 25 26 27
 56 5.857143    24 25 26 27 28
 57 5.877193    25 26 27 28
 58 5.896552    26 27 28 29
 59 5.915254    27 28 29
 60 5.933333    28 29 30
 61 5.950820    29 30
 62 5.967742    30 31
 63 5.984127    31
 64 6.000000    32
 65 6.030769    32
 66 6.060606    32 33
 67 6.089552    32 33
 68 6.117647    32 33 34
 69 6.144928    32 33 34
 70 6.171429    32 33 34 35
 71 6.197183    32 33 34 35
 72 6.222222    32 33 34 35 36
 73 6.246575    32 33 34 35 36
 74 6.270270    32 33 34 35 36 37
 75 6.293333    32 33 34 35 36 37
 76 6.315789    32 33 34 35 36 37 38
 77 6.337662    32 33 34 35 36 37 38
 78 6.358974    32 33 34 35 36 37 38 39
 79 6.379747    32 33 34 35 36 37 38 39
 80 6.400000    32 33 34 35 36 37 38 39 40
 81 6.419753    32 33 34 35 36 37 38 39 40
 82 6.439024    32 33 34 35 36 37 38 39 40 41
 83 6.457831    32 33 34 35 36 37 38 39 40 41
 84 6.476190    32 33 34 35 36 37 38 39 40 41 42
 85 6.494118    32 33 34 35 36 37 38 39 40 41 42
 86 6.511628    32 33 34 35 36 37 38 39 40 41 42 43
 87 6.528736    32 33 34 35 36 37 38 39 40 41 42 43
 88 6.545455    32 33 34 35 36 37 38 39 40 41 42 43 44
 89 6.561798    32 33 34 35 36 37 38 39 40 41 42 43 44
 90 6.577778    32 33 34 35 36 37 38 39 40 41 42 43 44 45
 91 6.593407    32 33 34 35 36 37 38 39 40 41 42 43 44 45
 92 6.608696    32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
 93 6.623656    32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
 94 6.638298    32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
 95 6.652632    32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
 96 6.666667    32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
 97 6.680412    33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
 98 6.693878    34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
 99 6.707071    35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
100 6.720000    36 37 38 39 40 41 42 43 44 45 46 47 48 49 50






Edited on October 25, 2019, 6:37 pm
  Posted by Charlie on 2019-10-25 18:33:40

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


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

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