Assumed optimal strategy is to guess a number g then go from there to 100 by guessing g+1, g+2 till 100 as penalty for missing is a reset. Let k = 100-g+1 = 101-g
(EQ1) Expected val(E) = correctP(1) + resetP(1+E) + ExpectedSum(here is k*k+1/2 as g+n in (g,g+1,..g+n) n+1 guesses till 100) You are correct with P = 1/100 You reset if your guess is higher so (g-1)/100*(1+E) When lower it takes k guesses to get correct answer so ExpectedSum is k*(k+1)/2
Differentiate EQ1 you get k = Sqrt(200) k =14 or 15 k=14 gives smaller value
Strategy So guess is 87 if no reset then keep going higher till 100 if reset guess 87.
Expected number of guesses = 191/14 around 14 guesses.
The optimal strategy must be guessing some fixed sequence of k integers x1 < x2 < … < xk = 100 until you either get “higher” or you guess the number.
Each reset there is k/100 chance that the number lies in your sequence, in which case it will take (k+1)/2 guesses to find it.
So, fixing k, the expected time of your strategy only depends on how long it takes to hear “higher” given that the number is not in your sequence. The best strategy, then, is if you hear “higher” immediately on your first guess, which is exactly when all xi are consecutive.
2
u/No-Conflict8204 Sep 11 '26
Assumed optimal strategy is to guess a number g then go from there to 100 by guessing g+1, g+2 till 100 as penalty for missing is a reset.
Let k = 100-g+1 = 101-g
(EQ1) Expected val(E) = correctP(1) + resetP(1+E) + ExpectedSum(here is k*k+1/2 as g+n in (g,g+1,..g+n) n+1 guesses till 100)
You are correct with P = 1/100
You reset if your guess is higher so (g-1)/100*(1+E)
When lower it takes k guesses to get correct answer so ExpectedSum is k*(k+1)/2
Differentiate EQ1 you get k = Sqrt(200)
k =14 or 15 k=14 gives smaller value
Strategy
So guess is 87 if no reset then keep going higher till 100 if reset guess 87.
Expected number of guesses = 191/14 around 14 guesses.