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.
(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 |
correction to previous post
