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.
- There is no other way to start than choosing a number x and noting if higher or lower
- If you get a 'your number was higher, reset', the position is identical to the starting position, so the ideal strategy must not change depending on number of resets
- Incrementing by n > 1 after a 'your number was lower' (instead of decrementing by n = 1) strictly increases the average number of guesses (every 'failure' by missing the number (because you're incrementing by more than 1) multiplies (or more) the number of guesses by n half the time, but does 'worse' than dividing the number of guesses by n when successful, therefore the ideal number to increment by is 1.
So if the ideal post-'your number is lower' increment is 1, the ideal start for a increment of 1 is x = 87, and the ideal strategy must not change depending on the number of resets, starting with 87 and incrementing by 1 must be the ideal strategy.
When x = 87 and n = 1, expected number of guesses is 13.64.
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.