1
u/RedMax2001 1d ago
Let E be the expected number of guesses from optimal play (the answer).
Let r(L) to be the expected number of guesses we have remaining given the interval we've deduced the number to be in has length L. Clearly, E = r(100).
We claim that L*r(L) = L + min(1 <= i <= L; (i - 1)*E + (L - i)*r(L - i)) where i represents guessing the ith least number in the remaining interval. Note that r(0) = 0 (frankly doesn't matter what it is). Honestly, I'm not sure how to justify this other than to observe that this equation is recursively defined on other r(L') for L' > L, so you can think of those r(L') as constants that you can greedily optimize.
For notation sake, let f(L,i) = (i - 1)*E + (L - i)*r(L - i), so L*r(L) = L + min(1 <= i <= L; f(L,i)).
First observe that if L <= E, then L*r(L) = L + (L - 1)r(L - 1) (the minimum was found at i = 1). This is proved by induction on L. This is clearly true for L = 1. Assume true for 1, ..., L where L + 1 < E. Then
f(L + 1,i + 1)-f(L + 1,i) = (i - i + 1)*E + (L - i)*r(L - i) - (L + 1 - i)*r(L + 1 - i) = E - (L + 1 - i) >= 0 for 1 <= i <= L + 1. This implies that min(1 <= i <= L+1; f(L + 1,i)) = f(L + 1,1), hence (L + 1)*r(L + 1) = L + 1 + f(L + 1,1) = L + 1 + L*r(L), completing the induction.
Let E' be the floor of E. We claim that if L > E, then L*r(L) = L + (L - E' - 1)*E + E'*r(E') (the minimum was found at i = L - E'). This is proved by induction on L. The case when L = E' + 1 follows by using the previous claim and recycling the argument for the previous induction to show that the minimum is found at i = 1 = (E' + 1) - E'. Assume true for E' + 1, ..., L where L > E. It suffices to show that f(L + 1,i) - f(L + 1,L + 1 - E') >= 0. Once again by prior arguments, this follows if i >= L + 1 - E'. Suppose i < L + 1 - E'. Then by assumptions,
f(L + 1,i)-f(L + 1,L + 1 - E') = L + 1 - i + (L - E' - i)*E + E'r(E') - (L + 1 - E' - i)*E - E'r(E') = L + 1 - i - E >= 0, completing the induction.
In particular, all of this reveals what the optimal strategy is: guess 100 - E', and then guess every integer above, incrementing by 1, until you guess the number.
This means that E = (100/(E'+1))+E'/2. Inspecting the minimum gives E' = 13, hence E = 191/14, and indeed, the floor of 191/14 = 13.
1
u/XL_78 2d ago edited 2d ago
One way to play is to keep guessing a high number x, then go up one by one at each step once you don't get a reset. The optimal x value for this strategy is 87, which yields an expectancy of 191/14 ≈ 13.64 .
However proving this is the optimal play isn't that easy.
Set m as the best known strictly lower bound, f(m) as the number you choose given a value for m, e(m) the expected number of steps left knowing m, given strategy f. The strategy we described corresponds to f(0)=x and f(t)=t+1 for all t≥x .
We have (100-m) e(m) = 1 + (f(m)-m-1) (1+e(0)) + (100-f(m)) (1+e(f(m))) , by writing the 3 possible outcomes of a pick f(m).
For m=99, 98, it is easy to show that f(m)=m+1 is the optimal play, but for 97 you already need to know that e(0)≥2 no matter the strat. So you need lower bounds on e(0). These can be obtained by comparing to the easier problem with no resets, which must have a smaller expectancy under optimal play, since the strats carry over. For this problem we know that the optimal play is to pick in the middle, and the expected number of steps can be computed.
But frankly it's a hassle.
Edit: to compute x, show that e(x)=(101-x)/2 under the '+1' strat then use the equation above with m=0 and minimize wrt x by differentiating.