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**