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.
Two additional thoughts about this very excellent problem.
1) In the actual part(b) solution, after guessing 69 and being told that N was higher, the strategy is to do a binary search of the remaining 31 numbers. 31 is of the form 2^x - 1, which means that you can always select the exact midpoint of the remaining range. I believe strongly that this is just a coincidence, and that for other ranges the maximum acceptable K can lead to an optimal strategy that does not involve a perfect binary search of 2^x - 1 possible values of N.
2) I was very interested in deriving the function which I called E(x), which is the number of expected guesses to find one number out of a range of size x. The full table is below. Note that denominator of the fraction is always x, and the numerator increases by 2, and then by 3, and then by 4, and then by 5, with the amount of the increase increasing only when x is a power of 2.
E(1) = 1/1
------------
E(2) = 3/2
E(3) = 5/3
------------
E(4) = 8/4
E(5) = 11/5
E(6) = 14/6
E(7) = 17/7
-------------
E(8) = 21/8
E(9) = 25/9
E(10) = 29/10
E(11) = 33/11
E(12) = 37/12
E(13) = 41/13
E(14) = 45/14
E(15) = 49/15
----------------
E(16) = 54/16
E(17) = 59/17
E(18) = 64/18
E(19) = 69/19
E(20) = 74/20
E(21) = 79/21
E(22) = 84/22
E(23) = 89/23
E(24) = 94/24
E(25) = 99/25
E(26) = 104/26
E(27) = 109/27
E(28) = 114/28
E(29) = 119/29
E(30) = 124/30
E(31) = 129/31
-----------------
E(32) = 135/32
E(33) = 141/33
E(34) = 147/34
E(35) = 153/35
E(36) = 159/36
E(37) = 165/37
E(38) = 171/38
E(39) = 177/39
E(40) = 183/40
E(41) = 189/41
E(42) = 195/42
E(43) = 201/43
E(44) = 207/44
E(45) = 213/45
E(46) = 219/46
E(47) = 225/47
E(48) = 231/48
E(49) = 237/49
E(50) = 243/50
E(51) = 249/51
E(52) = 255/52
E(53) = 261/53
E(54) = 267/54
E(55) = 273/55
E(56) = 279/56
E(57) = 285/57
E(58) = 291/58
E(59) = 297/59
E(60) = 303/60
E(61) = 309/61
E(62) = 315/62
E(63) = 321/63
------------------
E(64) = 328/64
E(65) = 335/65
E(66) = 342/66
E(67) = 349/67
E(68) = 356/68
E(69) = 363/69
E(70) = 370/70
E(71) = 377/71
E(72) = 384/72
E(73) = 391/73
E(74) = 398/74
E(75) = 405/75
E(76) = 412/76
E(77) = 419/77
E(78) = 426/78
E(79) = 433/79
E(80) = 440/80
E(81) = 447/81
E(82) = 454/82
E(83) = 461/83
E(84) = 468/84
E(85) = 475/85
E(86) = 482/86
E(87) = 489/87
E(88) = 496/88
E(89) = 503/89
E(90) = 510/90
E(91) = 517/91
E(92) = 524/92
E(93) = 531/93
E(94) = 538/94
E(95) = 545/95
E(96) = 552/96
E(97) = 559/97
E(98) = 566/98
E(99) = 573/99
E(100) = 580/100
E(101) = 587/101
Additional thoughts
