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!)

expectedtime to reach 1 for thefirsttime. 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." $\endgroup$2more comments