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.
I believe the part (b) breakeven is $11.75652. This compares to a part (a) breakeven of $8.60. The higher breakeven is justified because one can focus on just guessing the highest N values, and dropping out if the highest N values are not in play.
The strategy that justifies this high breakeven is to guess 69 initially. Let's say that you pay $11.75 to play.
If N is less than 69, stop after one turn, and lose $11.75
If N equals 69, pocket your $69 and walk away a big winner (net profit $57.25)
If N is greater than 69, use a binary search of the remaining 31 numbers to collect your prize. At no point does it make sense to stop playing. You will use at most 6 more guesses and are guaranteed at least $70. Expected winnings in this 3rd case is $85, against an expected total guesses of 160/31 at a total cost of $60.645, so the expected profit is $24.355.
In other words, you lose $11.75 with probability 69/101
, you make $58.25 with probability 1/101
, you make an expected $24.345 with probability 31/101.
Total expected profit is $0.015, because on each guess we paid $0.00652 less than breakeven.
In case you are interested, here is the breakeven for other initial guesses (calculated in Excel). In other words, if you are being charged $11.75 to play, you can only make an expected profit if you initially guess 69.
53 11.26380368
54 11.309375
55 11.35350318
56 11.3961039
57 11.43708609
58 11.47635135
59 11.5137931
60 11.54929577
61 11.58273381
62 11.61397059
63 11.64285714
64 11.66923077
65 11.69291339
66 11.71370968
67 11.73140496
68 11.74576271
69 11.75652174 <== highest amount that you would be willing to pay
70 11.71111111
71 11.65909091
72 11.6
73 11.53333333
74 11.45853659
75 11.375
76 11.28205128
77 11.17894737
78 11.06486486
79 10.93888889
80 10.8
81 10.64705882
82 10.47878788
83 10.29375
84 10.09032258
85 9.866666667
86 9.554794521
87 9.218309859
88 8.855072464
89 8.462686567
90 8.038461538
91 7.579365079
92 7.081967213
93 6.542372881
94 5.904347826
95 5.223214286
96 4.495412844
97 3.716981132
98 2.855769231
GREAT PUZZLE, TOMARKEN. I would have rated it a difficulty 4.
Edited on May 17, 2014, 3:27 pm
Part b solution (spoiler)
