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.

(In reply to re(3): Additional thoughts by Steve Herman)

All good points.

Problem 1 is a valid concern (I knew it seemed too simple!)  I'll have to rethink that part of it.

For problems 2 and 3, I thought $8.60 is the right number to think about, because we're looking for the maximum K for which we'd be willing to play variant (b), and we already know that this K must be greater than 8.60, since you'd be willing to pay more to play (b) than you'd be willing to pay to play (a).

So it's not about finding a new breakeven for part (b), I was just trying to show that:

- If K = 8.60 and your initial guess is greater than N, it doesn't make sense to continue if you're allowed to stop, and

- increasing K won't change this fact (keeping the range of N from 0 to 100), and

- the maximum K for which you'd be willing to play variant (b) is > 8.60. 

By doing so, I think that would've shown that you should always quit if your first guess is > N. 

Of course, if K is much lower (e.g. just a penny) then it does make sense to keep guessing, but the problem is asking for the greatest K for which you'd play, and which strategy you'd use.  Since we know K must be more than 8.60 we're not concerned with what happens at values less than that.  At least that made sense to me yesterday and still does today, but please do correct me if I'm mistaken, there will be no offense taken. :)

In any case, you're right that Problem 1 invalidates the whole thing anyway, so it's back to the drawing board.  As I was working out the problem for myself I had the same sense as you that the optimal strategy involves quitting after the first guess if it is greater than N, but I'd like to be able to prove it somehow as part of a complete solution.

Posted by tomarken on 2014-05-21 12:52:15