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

Home > Numbers
Guessing Game (Posted on 2014-05-16) Difficulty: 3 of 5
We decide to play the following game: An integer N will be randomly selected from the interval 0 - 100, inclusive. You try to guess N. After each guess, I tell you whether N is higher or lower than your guess.

If you successfully guess the integer, you win N dollars. Each guess costs you K dollars.

For each of the variants (a) and (b) below, what is the maximum value of K for which you'd be willing to play this game? Which strategy would you use to try to maximize your winnings in the long run?

(a) Once you start a round, you must continue until you guess N exactly.

(b) You may stop playing a round if you determine that N is too small to keep paying more money to guess N exactly. The money you've already spent on guesses is lost, but you may then start a new round with a new N.

No Solution Yet Submitted by tomarken    
Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution different part b solution (VB program) | Comment 7 of 18 |
I'm getting the following expected values for different K in part b:

 K   expected value
  2  39.14851
  3  34.25743
  4  29.72277
  5  25.54455
  6  21.72277
  7  18.15842
  8  14.63366
  9  11.32673
 10   8.26733
 11   5.45545
 12   2.89109
 13   0.57426
 14  -1.49505
 15  -3.46535
 16  -5.43564
 17  -7.40594
 18  -9.34653
 19  -11.13861
 20  -12.77228
 
In the 13 dollar range:

 13.00   0.57426
 13.01   0.55257
 13.02   0.53089
 13.03   0.50921
 13.04   0.48752
 13.05   0.46584
 13.06   0.44416
 13.07   0.42248
 13.08   0.40079
 13.09   0.37911
 13.10   0.35743
 13.11   0.33574
 13.12   0.31406
 13.13   0.29238
 13.14   0.27069
 13.15   0.24901
 13.16   0.22733
 13.17   0.20564
 13.18   0.18396
 13.19   0.16228
 13.20   0.14059
 13.21   0.11941
 13.22   0.09822
 13.23   0.07703
 13.24   0.05584
 13.25   0.03465
 13.26   0.01347
 13.27  -0.00772
 13.28  -0.02891
 13.29  -0.05010
 13.30  -0.07129
 13.31  -0.09248
 13.32  -0.11366
 13.33  -0.13485
 13.34  -0.15604
 13.35  -0.17723
 13.36  -0.19842
 13.37  -0.21960
 13.38  -0.24079
 13.39  -0.26198
 13.40  -0.28317
 13.41  -0.30386
 13.42  -0.32455
 13.43  -0.34525
 13.44  -0.36594
 13.45  -0.38663
 13.46  -0.40733
 13.47  -0.42802
 13.48  -0.44871
 13.49  -0.46941
 13.50  -0.49010
 13.51  -0.51079
 13.52  -0.53149
 13.53  -0.55218
 13.54  -0.57287
 13.55  -0.59356
 13.56  -0.61426
 13.57  -0.63495
 13.58  -0.65564
 13.59  -0.67634
 13.60  -0.69703
 13.61  -0.71723
 13.62  -0.73743
 13.63  -0.75762
 13.64  -0.77782
 13.65  -0.79802
 13.66  -0.81822
 13.67  -0.83842
 13.68  -0.85861
 13.69  -0.87881
 13.70  -0.89901
 13.71  -0.91921
 13.72  -0.93941
 13.73  -0.95960
 13.74  -0.97980
 13.75  -1.00000
 13.76  -1.02020
 13.77  -1.04040
 13.78  -1.06059
 13.79  -1.08079
 13.80  -1.10099
 13.81  -1.12069
 13.82  -1.14040
 13.83  -1.16010
 13.84  -1.17980
 13.85  -1.19950
 13.86  -1.21921
 13.87  -1.23891
 13.88  -1.25861
 13.89  -1.27832
 13.90  -1.29802
 13.91  -1.31772
 13.92  -1.33743
 13.93  -1.35713
 13.94  -1.37683
 13.95  -1.39653
 13.96  -1.41624
 13.97  -1.43594
 13.98  -1.45564
 13.99  -1.47535
 14.00  -1.49505

So I get 13.26 as the maximum with a positive expectation: about one and a third penny.

DefDbl A-Z
Dim crlf$
Dim guess(100, 100), minbid(100, 100)
Dim expVal(100, 100), k

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

Private Sub Form_Load()
 Text1.Text = ""
 crlf$ = Chr(13) + Chr(10)
 Form1.Visible = True
 DoEvents
 For k = 13 To 14 Step 0.01
   For span = 1 To 101
    For start = 0 To 100
      fin = start + span - 1
      If fin <= 100 Then
        If span = 1 Then
         expVal(start, fin) = start - k
         guess(start, fin) = start
         minbid(start, fin) = start
        Else
         bestev = -999999
         For firstcon = start To start + span - 1  ' first considered (stop if less)
           For g = firstcon To start + span - 1   ' temporary consideration of guess
             ev = g / span  ' hit it this guess
             If g > firstcon Then ev = ev + ((g - firstcon) / span) * expVal(firstcon, g - 1)
              ' considers prob. of new subspan times expected value of that subspan, previously
              ' calculated as we're building bottom up
             If g < start + span - 1 Then ev = ev + (((start + span - 1) - g) / span) * expVal(g + 1, start + span - 1)
              ' likewise for the subspan above the guess under consideration
             ev = ev - k  ' pay the bill for the try
             If ev > bestev Then ' consider only the guess that gives the highest expectation
               bestev = ev: bestfirstcon = firstcon: bestg = g
             End If
           Next g
         Next firstcon
         guess(start, fin) = bestg
         minbid(start, fin) = bestfirstcon
         expVal(start, fin) = bestev
        End If
      
      End If
    Next start
   Next span
   Text1.Text = Text1.Text & mform(k, "###.00  ") & mform(expVal(0, 100), "#0.00000") & crlf
   DoEvents
 Next k
End Sub

Strategy comes from a table of expected values, built from the bottom (range of only 1) up.

Edited on May 17, 2014, 4:28 pm
  Posted by Charlie on 2014-05-17 16:15:35

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 (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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