This is a guest post by Andrew Jamieson, based on a problem we solved together.

## Introduction #

Suppose you are racing in on dimension, trying to get from 0 to 1 as quickly as possible. You start with a speed of 1. However at any time you choose, you may press a button that will instantly teleport you back to the origin, and multiply your speed by $(1+2r)$, where $r$ is the location at which you pressed the button.

If you can press this button as many times as you like, how fast can you finish the race, and when are the optimal times to press this? And how do things change if the multiplier is instead $(1+kr)$?

This question came up while thinking about traditional idle video games in which you can spend resources and purchase upgrades to increase your resource gathering rate, however these can generally only be activated by pressing restart and sacrificing all your resources.

## Exploration #

To solve this problem, it pays to do a bit of exploratory analysis.

### To Press or Not to Press? #

The first question that needs answering is whether it is worth pressing the button at all? To work this out, we can consider a simplified model where we plan to press the button exactly once at point r. In this case the total time taken to complete the race is

• The time taken to travel a distance $r$ while travelling at a speed of $1$:
$\frac{\mathrm{distance}}{\mathrm{speed}}=\frac{r}{1}.$
• The time taken to travel from the origin to $1$ while travelling at $(1+2r)$:
$\frac{\mathrm{distance}}{\mathrm{speed}}=\frac{1}{(1+2r)}.$

Adding these together gives the total time:
[eqTimeOnePress]: $T = r + \frac{1}{1+2r}.$

We can find the optimal $r$ by solving for when the derivative is zero:
$\frac{\mathrm{d}T}{\mathrm{d}r} = 1 - \frac{2}{(1+2r)^2} =0.$
This happens when
\begin{aligned}0 &= (1+2r)^2 - 2, \\ &= 4r^2+4r-1,\end{aligned}
which has solution given by the quadratic formula:
$r = \frac{-1 \pm \sqrt{2}}{2}.$
One of these solutions is negative, so not relevant to our problem. The positive solution is
$r \approx 0.2071.$
Substituting this into [eqTimeOnePress] then gives a time of
$T = \frac{-1 + \sqrt{2}}{2} + \frac{1}{1+2(\frac{-1 + \sqrt{2}}{2})} \approx 0.9142.$
This is less than 1, so it clearly does pay to press the button at least once. Now the question gets more complicated. How many times should we press the button, and when should we do so?

### Multiple presses #

Now let's consider multiple presses. For reasons that will make sense later, I'm going to number the presses counter intuitively. The location of the last press will be denoted $r_1$, the one immediately before that will be $r_2$, and so on and so forth. The total time taken when using $n$ presses will be denoted by $T_n$.

To start with, we'll assume two presses while we build some intuition for the problem. The total time to complete the race becomes:

• The time to travel until the first press at $r_2$ with speed $1$:
$\frac{\mathrm{distance}}{\mathrm{speed}}=\frac{r_2}{1}.$
• The time taken to travel until the second press at $r_1$ with speed $(1+2r_1)$:
$\frac{\mathrm{distance}}{\mathrm{speed}}=\frac{r_1}{(1+2r_2)}.$
• The time taken to travel from $0$ to $1$ with speed $(1+2r_2)(1+2r_1)$:
$\frac{\mathrm{distance}}{\mathrm{speed}}=\frac{1}{(1+2r_2)(1+2r_1)}.$

Adding these together gives the total time for two presses:
[eqTimeTwoPresses]: $T_2 = r_2 + \frac{r_1}{(1+2r_2)} + \frac{1}{(1+2r_2)(1+2r_1)}.$
Now optimising this using derivatives is a multivariate calculus problem that would be a pain to do by hand. But you can fire up Python or Mathematica to get a numerical solution (see the appendix for code):
\begin{aligned} r_1 &\approx 0.2071 \\ r_2 &\approx 0.1761.\end{aligned}

The last press, $r_1$, is at the same place as when we were only using one press! This is quite surprising. Let's try again with three presses and see if the pattern continues. In this case the total time is
[eqTimeThreePresses]: $T_3 = r_3 + \frac{r_2}{(1+2r_3)} + \frac{r_1}{(1+2r_3)(1+2r_2)} + \frac{1}{(1+2r_3)(1+2r_2)(1+2r_1)},$
and the optimal times are
\begin{aligned} r_1 &\approx 0.2071 \\ r_2 &\approx 0.1761\\ r_3 &\approx 0.1528.\end{aligned}
Clearly this pattern is continuing. Why? Surely it would make sense that optimising across multiple presses would require adjusting all of them, not just the newest one.

Well let's take a look at equations for the times $T_1,T_2,T_3$. In the case of a single press, what would happen if we started at a different speed, say $s$? Well then [eqTimeOnePress] becomes:
$T_1 = \frac{1}{s}(r_1 + \frac{1}{1+2r_1}).$
This however is only a scaling factor. Scaling factors don't change the location of the optimal point, meaning the location of the press does not depend on the incoming speed.

Now let's re-examine [eqTimeTwoPresses] by cleverly factorising it:
\begin{aligned} T_2 &= r_2 + \frac{r_1}{(1+2r_2)} + \frac{1}{(1+2r_2)(1+2r_1)}, \\ &= r_2 + \frac{1}{(1+2r_2)}\left(r_1 + \frac{1}{(1+2r_1)}\right), \\ &= r_2 + \frac{1}{(1+2r_2)}T_1. \end{aligned}
Remember that $r_2$ is the first press, and $r_1$ the second. Due to the scaling argument we made above, the optimal location for the second press $r_1$ is completely independent of the first press $r_2$. However from this formula, $r_2$ is determined by $r_1$ due to the $T_1$ in the equation above.

Similarly for [eqTimeTwoPresses]:
\begin{aligned}T_3 &= r_3 + \frac{r_2}{(1+2r_3)} + \frac{r_1}{(1+2r_3)(1+2r_2)} + \frac{1}{(1+2r_3)(1+2r_2)(1+2r_1)}, \\ &= r_3 + \frac{1}{(1+2r_3)}\left(r_2 + \frac{1}{(1+2r_2)}(r_1 + \frac{1}{(1+2r_1)})\right), \\ &= r_3 + \frac{1}{(1+2r_3)}\left(r_2 + \frac{1}{(1+2r_2)}T_1\right), \\ &= r_3 + \frac{1}{(1+2r_3)}T_2. \end{aligned}

This confirms the observations that seemed strange before. It turns out that the optimal press value can be calculated purely based on the optimal press values that come after it, and not those before it. Hopefully now you can see why we chose that indexing system.

## Optimal solution #

### Sequential formula #

Generalising the analysis in the previous section, we have the result:
[eqGeneralisedSequence]: $T_n = r_n + \frac{1}{1+2r_n}T_{n-1}.$
Solving for the optimal point when the derivative is zero, and once-again exluding a non-physical solution, gives
[eqGeneralisedRestarts]: $r_n = \frac{\sqrt{2}\sqrt{T_{n-1}}-1}{2}.$

[eqGeneralisedSequence] and [eqGeneralisedRestarts] together can be used to generate the infinite set ${r_n}$ of every restart. Here are the first ten:

$r_1$ $0.2071$
$r_2$ $0.1761$
$r_3$ $0.1528$
$r_4$ $0.1346$
$r_5$ $0.1202$
$r_6$ $0.1084$
$r_7$ $0.0987$
$r_8$ $0.0905$
$r_9$ $0.0835$
$r_{10}$ $0.0775$

### General solution and time #

At this point, it's reasonable to investigate how the speed multiplier affects the results, rather than just looking at $k=2$. For this we can use the generalised form of [eqGeneralisedSequence]: :
$T_n = r_n + \frac{1}{1+kr_n}T_{n-1}.$
Once again solving for optimal point at zero derivative gives:
$r_n = \frac{\sqrt{k}\sqrt{T_{n-1}}-1}{k}.$
Combining these gives us
$T_n = \frac{\sqrt{k}\sqrt{T_{n-1}}-1}{k} + \frac{1}{1+k\left(\frac{\sqrt{k}\sqrt{T_{n-1}}-1}{k}\right)}T_{n-1},$
which simplifies to
[eqGeneralisedCombined]: $T_{n}=\frac{-1+2\sqrt{kT_{n-1}}}{k}.$

In the figure below we plot $T_{1000}$ for values of $k$ ranging from $1$ to $10$ (including decimals). See the appendix for Python and Mathematica code to generate this. This seems very well-behaved! Motivated by this if we investigate a bit closer, when looking at the actual values, a suspicious looking pattern of the total optimal time required to complete the race is revealed:

$k$ $T_{1000}$ $1/k$
$1$ $1.0$ $1$
$2$ $0.5002$ $0.5$
$3$ $0.3334$ $0.3333$
$4$ $0.2501$ $0.25$
$5$ $0.2001$ $0.2$
$6$ $0.1667$ $0.1667$
$7$ $0.1429$ $0.1429$
$8$ $0.1251$ $0.125$
$9$ $0.1112$ $0.1111$
$10$ $0.1000$ $0.1$

To see whether this pattern is real, we just need to solve for the total time taken when using infinitely many presses, which can be done by taking the limit of both sides of [eqGeneralisedCombined].
\begin{aligned}T_{\infty} &= \lim_{n\rightarrow\infty}T_n, \\ &= \lim_{n\rightarrow\infty}\frac{-1+2\sqrt{kT_{n-1}}}{k}, \\ &= \frac{-1+2\sqrt{kT_{\infty}}}{k}.\end{aligned}
Let's solve this for $T_{\infty}$:
\begin{aligned}kT_{\infty}+1 &= 2\sqrt{kT_{\infty}}, \\ k^2T_{\infty}^2+2kT_{\infty}+1 &=4kT_{\infty}, \\ (kT_{\infty}-1)^2 &=0.\end{aligned}
This has solution:
$T_{\infty}=\frac{1}{k}.$

## Conclusion #

The answer to the problem is that you should press the button, and the more times you press it the faster you can complete the race. For $k$ greater than $1$, the formula below can be used to find the time taken, and optimal places to stop:
\begin{aligned}T_n &= r_n + \frac{1}{1+kr_n}T_{n-1} \\ r_n &= \frac{\sqrt{k}\sqrt{T_{n-1}}-1}{k}.\end{aligned}
However, as the number of presses increases, there are diminishing returns. In the limit of infinite presses, the total time taken to complete the race will approach $1/k$.

It is worth thinking about how we found the solution. To get an initial feel for the problem we did some numerical searches. These revealed a pattern in the solution, that the stopping locations for $n+1$ stops were the same as the times for $n$ stops (with one more added). This made the problem much easier to solve analytically, since we only had to worry about one stopping location at a time. It's always nice to see numerics inform analytics, and vice versa.

A formula like above, expressing $T_n$ in terms of $T_{n-1}$, is called a recurrence relation. A natural question to ask is if we can solve this, and obtain a formula for $T_n$ in terms of just $n$ alone. Unfortunately this recurrence relation is nonlinear due to the square root term $\sqrt{T_{n-1}}$. Much like nonlinear differential equations, nonlinear recurrence relations are exteremely difficult to solve, and we usually have to resort to numerics. It is unlikely that an explicit formula exists, though please let us know if you find one or have any ideas!

## Appendix#

Here you'll find Mathematica and Python code you can use to reproduce results from this article.

### Finding the stopping times #

These codes compute the stopping times $r_j$ for a fixed number of stops.

#### Python #

import mathimport matplotlib.pyplot as pltimport numpy as npimport scipydef total_time_with_restarts(r, k):    """Calculates the total time taken to complete the race given     the location of restarts and the multiplication parameter k.        Variables:    r: iterable of numbers representing the location of the restart    k: multiplication parameter"""    sum_list = []    for i in range(len(r)):        divisor = []        for j in range(i):            divisor.append(1+k*r[j])        sum_list.append(r[i] / math.prod(divisor))    sum_list.append(1/math.prod((1+k*r[j] for j in range(len(r)))))    return sum(sum_list) k=2for number_of_restarts in range(1, 11):    opt = scipy.optimize.minimize(total_time_with_restarts,       0.2 * np.ones(number_of_restarts), args=(k,),       bounds=[(0,1) for _ in range(number_of_restarts)])    #Prints the total optimal time along with the location     # of the restarts in press order.    print(number_of_restarts, total_time_with_restarts(opt.x,k), opt.x)

#### Mathematica #

(* Formula for the time given nR stops *)time[nR_] :=  Sum[If[j > 0, r[j], 1]/   Product[1 + 2 r[nR - i + 1], {i, 1, nR - j}], {j, nR, 0, -1}];(* Bounds on the numerical optimisation *)bounds[nR_] := Table[0 <= r[j] <= 1, {j, 1, nR}];(* Numerically minimise time[nR] *)min[nR_] :=   FindMinimum[Reverse@Append[bounds[nR], time[nR]],    Table[r[j], {j, 1, nR}]];(* First ten stopping times *)Last /@ Last@min

### Computing T1000 #

Here is code you can use to compute and plot the $T_{1000}$ for various $k$.

#### Python #

import mathimport matplotlib.pyplot as pltimport numpy as npimport scipydef optimal_time(k, presses):    """Returns the optimal race completion time given the     multiplication factor and numer of button presses used.        Variables:    k: multiplication parameter    presses: number of button presses."""    if k == 0:        return 1    time=1    for _ in range(10000):        r = (math.sqrt(k)*math.sqrt(time) - 1)/k        r = r if r>0 else 0        time = r + time/(1+k*r)    return time    presses = 1000inputvec = [n/100 for n in range(0, 1000)]plt.plot(inputvec, [optimal_time(k, presses) for k in inputvec])plt.xlabel("k")plt.ylabel("Total Time")

#### Mathematica #

(* Find T_(n+1) given T_n and k. *)(* You want a . after 2 so it evaluates numerically,    which is much faster than exact evaluation *)Tnp1[Tn_, k_] := (-1 + 2. Sqrt[k Tn])/k;(* Compute T_1000 by Nesting T_(n+1) 1000 times *)(* Use a Table to do this for all k *)T1000Data = Table[{k, Nest[Tnp1[#, k] &, 1, 1000]}, {k, 1, 10, 0.1}];(* Plot the T_1000 *)ListPlot[T1000Data, AxesLabel -> {"k", None}, PlotLabel -> "T1000 for various k", LabelStyle -> Directive[FontSize -> 20, FontColor -> Black], ImageSize -> Large, Ticks -> {Range, Range[0.2, 1, 0.2]}, AxesOrigin -> {1, 0}]