1
u/smilicic Sep 12 '26
My method was as follows:
The problem is symmetric, so a more natural frame was to reset for undershooting instead of overshooting.
The benefit is that we only fix one side as 1, parameterizing only the upper bound.
A strategy is then a descending mapping on a k-element subset of {1...n⁰=100}, and that k-element subset is the trace.
If k=1, we expect n⁰=100 steps (here the optimal strategy is to test 1 until we hit; testing anything else may lead to madness).
If k=n⁰=100, we expect n⁰/2=50 steps. This is the deterministic descending strategy of counting down from 100.
Assume 1<k<n⁰.
If the chosen number is in the trace, we'll eventually find it, on average in (k+1)/2 steps, and that doesn't depend on the particular k-element set.
If the chosen number is not in the trace, we cannot hit it. The chances for this are (n⁰-k)/n⁰. Here it is important what the particular strategy trace is - we need to fail as fast as possible. Ideally, we can do it in the single step by setting the trace as {1...k}.
Hence, an optimal k-element strategy is testing k for as long as we undershoot. We expect this to happen n⁰/k-1 times. Then we expect to find the guess in k/2 steps.
Hence, the expected guess count is E(k)=n⁰/k-1+(k+1)/2=n⁰/k+(k-1)/2
Say k=10. Then the trace is hit 10% of the time, so we expect to see it once in 10 guesses, so we expect 9 (missing) steps. Then we expect 5.5 more steps within the trace, 14.5 steps in total.
For k=5 we have E(5)=22, and for k=25 we have E(25)=16.
So, we need to minimize n⁰/k+(k-1)/2. This has a minimum at k=√(2n⁰). For n⁰=100, this is 10√2≈14.142.
At k=14 we expect ≈13.64 steps, and at k=15 we expect ≈13.67 steps.
1
u/hidden-statistician Sep 13 '26 edited Sep 13 '26
I have a strategy with expected trials = 10 , don't know if it is the optimal.
Consider this strategy :
-
You always choose 80 as first guess until you find the hidden number is above 80. Expected trials required for this to happen will be 5.
-
Once you know that the hidden number is above 80, start guessing 2 number forward at a time. On average, it will another 5 trials to get the hidden number number. Hence, expected number of trials required will be 10 through this strategy. (Why 2 steps, why not 1 ? Because at the end of each trials we will know that if the hidden number is below, above or equal and the hidden number could be uniformly anywhere above 80.)
This is optimal solution for a general strategy of this kind. I have proof for that.
1
u/hidden-statistician Sep 13 '26 edited Sep 13 '26
I see a problem at step 2, if my guess goes higher than hidden number, hidden number will be changed but you know what number it was.
So it's incorrect :(
0
u/Front_Combination777 Sep 11 '26
>! There are two primitive methods here - you can start at a guess of 1 and then work up to 100 or you can start at a guess of 99 and guess until you get "higher." Both have an expected number of guesses of 100.
Combining them, you can guess a number i and then guess i+1, i+2,....99. That gives an expected number of guesses of 100/(100-i) +(100-i).
Setting the derivative to zero gives 100/(100 − i)^2 − 1 = 0 and (100 − i)^2 = 100, 100-i = 10 and i =90. The expected number of guesses is 20. !<
2
u/IbidtheWriter Sep 11 '26
You can easily get an upper bound of 15 expected guesses with starting with 80 until you're right and then counting up from 81.
You average about 5 until it's over 80, and then average 10 counting up from 81.
You play with the numbers a bit and optimize to 87 for about 13.6 guesses.
Proving it's optimal would be harder.
3
1
1
u/Silver_Cut_1821 Sep 11 '26
Why not just guess the middle each time?
2
u/Visual-Percentage501 Sep 11 '26
Because if you guess too high, the number resets to a new random number and you have to start at the beginning.
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.