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.)
re(2): Full solution: 15 and beyond | Comment 8 of 10 |
(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

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


Search:
Search body:
Forums (3)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
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