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 Part a (pencil and paper spoiler) | Comment 3 of 18 |
Part A isn't too hard to do exactly using pencil & paper.

Let E(n) = Expected number of guesses after we have narrowed it down to a range of n

Well,  Starting with 101 guesses, we will guess the midpoint.  We have no more guesses with probability 1/101, and E(50) guesses otherwise.

In other words, E(101) = 1 + E(50)*(100/101)

Starting with a range of 50, we guess a number that is the midpoint + .5.  We have no more guesses with probability 1/50, E(24) guesses with probability 24/50, otherwise E(25).

In other words, E(50) = 1 + E(24)*(24/50) + E(25)*(25/50)

Similarly, 
E(25) = 1 + E(12)*24/25
E(24) = 1 + E(11)*11/24 + E(12)*12/24
E(12) = 1 + E(5)*5/12 + E(6)*6/12
E(11) = 1 + E(5)*10/11
E(6)  = 1 + E(2)*2/6 + E(3)*3/6
E(5)  = 1 + E(2)*4/5
E(3)  = 1 + E(1)*2/3
E(2)  = 1 + E(1)*1/2
E(1)  = 1

Substituting,
E(2) = 3/2
E(3) = 5/3
E(5) = 11/5
E(6) = 14/6
E(11) = 33/11
E(12) = 37/12
E(24) = 94/24
E(25) = 99/25
E(50) = 243/50
E(101) = 587/101

Expected payoff = $50, 
so breakeven = $50/E(101) = 5050/587 = $8.60306643952.
I would play if K = $8.60, but not if it was $8.61

The part b strategy is much more interesting, as one should not start guessing at the midpoint, I think.  A point above the midpoint makes more sense.

Edited on May 17, 2014, 2:36 am
  Posted by Steve Herman on 2014-05-17 02:32:55

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