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: Full solution: 15 and beyond by Steven Lord)
Following Steve Herman's lead I used dynamic programming to follow up on your suggestion of finding the procedure and expected value when you merely wish to know the answer, rather than to follow through and correctly guess the answer.
However the program has a fatal flaw: for n=1, you already know the answer and so it takes zero tries. This affects all subsequent expected values and optimal strategies. More in a later post.
The program
DefDbl A-Z
Dim crlf$, expected(30), best(30, 30), n
Private Sub Form_Load()
Form1.Visible = True
Text1.Text = ""
crlf = Chr$(13) + Chr$(10)
expected(1) = 1: best(1, 0) = 1: best(1, 1) = 1
expected(2) = 1: best(2, 0) = 1: best(2, 1) = 1
For n = 3 To 30
findbest
Text1.Text = Text1.Text & mform(n, "##0") & mform(expected(n), " 0.000000") & " "
For i = 1 To best(n, 0)
Text1.Text = Text1.Text & mform(best(n, i), "##0")
Next
Text1.Text = Text1.Text & crlf
Next
Text1.Text = Text1.Text & crlf & tot & " done"
End Sub
Sub findbest()
lowSoFar = 99999
For try = 1 To n / 2
DoEvents
avrg = 1 + (try / n) * expected(try) + ((n - try) / n) * expected(n - try)
s$ = mform(avrg, "0.000000")
If avrg <= lowSoFar + 0.00000001 Then
expected(n) = avrg
If s <> lowform$ Then
best(n, 0) = 0
lowform$ = s
End If
lowSoFar = avrg
best(n, 0) = best(n, 0) + 1
best(n, best(n, 0)) = try
End If
Next try
End Sub
Function mform$(x, t$)
a$ = Format$(x, t$)
If Len(a$) < Len(t$) Then a$ = Space$(Len(t$) - Len(a$)) & a$
mform$ = a$
End Function
does find divergence from the binary search:
The first two rows were hard coded into the program and the remainder were calculated based on the prior results:
n expected best first picks
guesses
1 1 1
2 1 1
3 2.000000 1
4 2.000000 2
5 2.600000 2
6 2.666667 2
7 3.000000 3
8 3.000000 4
9 3.333333 4
10 3.400000 4
11 3.636364 4 5
12 3.666667 4 6
13 3.846154 5 6
14 3.857143 6
15 4.000000 7
16 4.000000 8
17 4.176471 8
18 4.222222 8
19 4.368421 8 9
20 4.400000 8 10
21 4.523810 8 9 10
22 4.545455 8 10
23 4.652174 8 9 10 11
24 4.666667 8 10 12
25 4.760000 9 10 11 12
26 4.769231 10 12
27 4.851852 11 12 13
28 4.857143 12 14
29 4.931034 13 14
30 4.933333 14
Note that 3 is not optimal for n=6, and 5 is not optimal for n=10, nor 7 for n=14, nor 9 for n=18, etc. The pattern for odd binary results continues at least through n=100.
Edited on October 25, 2019, 6:28 pm
|
|
Posted by Charlie
on 2019-10-25 11:53:07 |
re(2): Full solution: 15 and beyond
