# Optimal search puzzle

Consider the following puzzle: On the integer line from 1 to $$t$$ (top, let's say 1000 for this example), you have two operators: uniform random on 1 to $$t$$, and subtract 1. What is the optimal algorithm to reach 1 with the least number of operators?

For example, if you do one random sample and then always count down, on average it will take 500 steps (or maybe 501 if you count the initial step). An obviously better algorithm is to pick a random value until you get below some threshold, and then count down.

We programmed this for $$t=1000$$ and the best threshold was 42. Interestingly (perhaps obviously) below this you get a power function (about $$x^{-0.812}$$), and above this it linearly increases to 500.

Two questions: 1. Is there a better algorithm in general? 2. If ours is optimal what is the general equation for the minimum threshold? (Implicit third question: Presumably someone's already asked this...pointer please!)

• Can you specify what you mean by optimality? For example, do you want to minimize the expected value of the number of steps that we take to reach 1? Commented Sep 24, 2023 at 16:33
• It's written in an amateurish way, but I don't think this question is completely trivial, so the downvotes seems excessive to me. Commented Sep 24, 2023 at 17:48
• What is amateurish about they writing? (Not defensive; Trying to learn.) The problem actually was posed by my 14 year old son, so perhaps it’s not too surprising that it’s amateurish as he’s an amateur. :-) Commented Sep 25, 2023 at 2:16
• @jackisquizzical Here's how I might write your first paragraph. Fix a positive integer $t$. Let $D$ denote the operation of replacing a given integer $n$ by $n-1$, and let $R$ denote the operation of replacing a given integer $n$ by a positive integer chosen uniformly at random from $\{1,2,\ldots,t\}$. Given a starting value $n_0$, we may apply any sequence of $D$'s and $R$'s we like to $n_0$. Our goal is to minimize the expected time to reach 1 for the first time. What is the optimal sequence of $D$'s and $R$'s? Commented Sep 27, 2023 at 20:36
• (continued) This rewrite is wordier, but it spells out explicitly that you're applying the operations sequentially to a single starting value, and that what you're trying to minimize is the expected time to reach 1 for the first time. These details can be plausibly inferred from your more concise description, but it's more "professional" to spell out such details explicitly, so as to remove all doubt about your intended question. There is also no need to use the word "puzzle." Commented Sep 27, 2023 at 23:32

You can solve the problem via dynamic programming. For $$n\in\{1,\dots,t\}$$, let $$V(n)$$ be the minimum expected number of steps starting from $$n$$. Then $$V(1)=0$$ and otherwise $$V(n) = 1+\min\left(\frac{1}{t}\sum_{k=1}^t V(k), V(n-1)\right).$$
Because $$V(n)$$ appears on both sides, you cannot just iterate the recursion. Instead, you can use linear programming as follows. The problem is to maximize $$\sum_{n=1}^t V(n)$$ subject to linear constraints \begin{align} V(1) &= 0 \\ V(n) &\le 1 + \frac{1}{t}\sum_{k=1}^t V(k) \\ V(n) &\le 1 + V(n-1) \\ \end{align} Here's a plot of $$V(n)$$ for $$n\in\{1,\dots,1000\}$$:
In particular, $$V(n)= \begin{cases} n-1 &\text{for n \le 45}, \\ 44+2/9 &\text{otherwise}. \\ \end{cases}$$
Because using the random operator destroys any potential gain from a previous subtraction, the optimal strategy must look like the one stated in the question. The solution of @RobPratt showed that in this case $$V(n) = 1+\min\left(\frac{1}{t}\sum_{k=1}^t V(k), V(n-1)\right).$$ For $$t=1000$$ he showed that the threshold value is $$m=44$$ and for $$n\geq m+2$$ one has a constant $$V(n) = m+\xi$$ with $$\xi=2/9$$, whilst for $$n\leq m+1$$ one has $$V(n)=n-1$$. For general $$t$$ one can use the equation to infer that for some $$0\leq \xi<1$$ $$V(m+2) ~=~ 1+\frac{1}{t}\sum_{k=1}^t V(k) ~=~1+ \frac{1}{t}\sum_{k=1}^{m+1} (k-1) + \frac{(m+\xi) (t-m-1)}{t}.$$ Because $$V(m+2) =m+\xi$$ This gives $$m+\xi ~=~ 1+ \frac{1}{t} {m+1 \choose 2} + \frac{(m+\xi) (t-m-1)}{t},$$ and after solving for $$\xi$$: $$\xi= \frac{t}{m+1} -\frac{m}{2},~~{\rm or}~~0\leq \frac{t}{m+1} -\frac{m}{2}<1.$$ Rearranging gives $${m+1 \choose 2} \leq t< {m+2 \choose 2},$$ which uniquely defines the threshold $$m$$ as $$m ~=~ \left\lfloor \frac{\sqrt{8\,t+1} -1}{2} \right\rfloor.$$