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)(1+2r), where rr 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)(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 rr while travelling at a speed of 11:
    distancespeed=r1.\frac{\mathrm{distance}}{\mathrm{speed}}=\frac{r}{1}.
  • The time taken to travel from the origin to 11 while travelling at (1+2r)(1+2r):
    distancespeed=1(1+2r).\frac{\mathrm{distance}}{\mathrm{speed}}=\frac{1}{(1+2r)}.

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

We can find the optimal rr by solving for when the derivative is zero:
dTdr=1−2(1+2r)2=0. \frac{\mathrm{d}T}{\mathrm{d}r} = 1 - \frac{2}{(1+2r)^2} =0.
This happens when
0=(1+2r)2−2,=4r2+4r−1,\begin{aligned}0 &= (1+2r)^2 - 2, \\ &= 4r^2+4r-1,\end{aligned}
which has solution given by the quadratic formula:
r=−1±22.r = \frac{-1 \pm \sqrt{2}}{2}.
One of these solutions is negative, so not relevant to our problem. The positive solution is
r≈0.2071.r \approx 0.2071.
Substituting this into [eqTimeOnePress] then gives a time of
T=−1+22+11+2(−1+22)≈0.9142.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 r1r_1, the one immediately before that will be r2r_2, and so on and so forth. The total time taken when using nn presses will be denoted by TnT_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 r2r_2 with speed 11:
    distancespeed=r21.\frac{\mathrm{distance}}{\mathrm{speed}}=\frac{r_2}{1}.
  • The time taken to travel until the second press at r1r_1 with speed (1+2r1)(1+2r_1):
    distancespeed=r1(1+2r2).\frac{\mathrm{distance}}{\mathrm{speed}}=\frac{r_1}{(1+2r_2)}.
  • The time taken to travel from 00 to 11 with speed (1+2r2)(1+2r1)(1+2r_2)(1+2r_1):
    distancespeed=1(1+2r2)(1+2r1).\frac{\mathrm{distance}}{\mathrm{speed}}=\frac{1}{(1+2r_2)(1+2r_1)}.

Adding these together gives the total time for two presses:
[eqTimeTwoPresses]: T2=r2+r1(1+2r2)+1(1+2r2)(1+2r1).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):
r1≈0.2071r2≈0.1761.\begin{aligned} r_1 &\approx 0.2071 \\ r_2 &\approx 0.1761.\end{aligned}

The last press, r1r_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]: T3=r3+r2(1+2r3)+r1(1+2r3)(1+2r2)+1(1+2r3)(1+2r2)(1+2r1),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
r1≈0.2071r2≈0.1761r3≈0.1528.\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 T1,T2,T3T_1,T_2,T_3. In the case of a single press, what would happen if we started at a different speed, say ss? Well then [eqTimeOnePress] becomes:
T1=1s(r1+11+2r1). 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:
T2=r2+r1(1+2r2)+1(1+2r2)(1+2r1),=r2+1(1+2r2)(r1+1(1+2r1)),=r2+1(1+2r2)T1.\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 r2r_2 is the first press, and r1r_1 the second. Due to the scaling argument we made above, the optimal location for the second press r1r_1 is completely independent of the first press r2r_2. However from this formula, r2r_2 is determined by r1r_1 due to the T1T_1 in the equation above.

Similarly for [eqTimeTwoPresses]:
T3=r3+r2(1+2r3)+r1(1+2r3)(1+2r2)+1(1+2r3)(1+2r2)(1+2r1),=r3+1(1+2r3)(r2+1(1+2r2)(r1+1(1+2r1))),=r3+1(1+2r3)(r2+1(1+2r2)T1),=r3+1(1+2r3)T2.\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]: Tn=rn+11+2rnTn−1.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]: rn=2Tn−1−12.r_n = \frac{\sqrt{2}\sqrt{T_{n-1}}-1}{2}.

[eqGeneralisedSequence] and [eqGeneralisedRestarts] together can be used to generate the infinite set rn{r_n} of every restart. Here are the first ten:
r1r_1 0.20710.2071
r2r_2 0.17610.1761
r3r_3 0.15280.1528
r4r_4 0.13460.1346
r5r_5 0.12020.1202
r6r_6 0.10840.1084
r7r_7 0.09870.0987
r8r_8 0.09050.0905
r9r_9 0.08350.0835
r10r_{10} 0.07750.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=2k=2. For this we can use the generalised form of [eqGeneralisedSequence]: :
Tn=rn+11+krnTn−1.T_n = r_n + \frac{1}{1+kr_n}T_{n-1}.
Once again solving for optimal point at zero derivative gives:
rn=kTn−1−1k.r_n = \frac{\sqrt{k}\sqrt{T_{n-1}}-1}{k}.
Combining these gives us
Tn=kTn−1−1k+11+k(kTn−1−1k)Tn−1,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]: Tn=−1+2kTn−1k.T_{n}=\frac{-1+2\sqrt{kT_{n-1}}}{k}.

In the figure below we plot T1000T_{1000} for values of kk ranging from 11 to 1010 (including decimals). See the appendix for Python and Mathematica code to generate this.

A plot of T1000 for values of k between 1 and 10. This is a decreasing curve, following the shape of T1000=1/k

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:

kk T1000T_{1000} 1/k1/k
11 1.01.0 11
22 0.50020.5002 0.50.5
33 0.33340.3334 0.33330.3333
44 0.25010.2501 0.250.25
55 0.20010.2001 0.20.2
66 0.16670.1667 0.16670.1667
77 0.14290.1429 0.14290.1429
88 0.12510.1251 0.1250.125
99 0.11120.1112 0.11110.1111
1010 0.10000.1000 0.10.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].
T∞=lim⁡n→∞Tn,=lim⁡n→∞−1+2kTn−1k,=−1+2kT∞k.\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∞T_{\infty}:
kT∞+1=2kT∞,k2T∞2+2kT∞+1=4kT∞,(kT∞−1)2=0.\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∞=1k.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 kk greater than 11, the formula below can be used to find the time taken, and optimal places to stop:
Tn=rn+11+krnTn−1rn=kTn−1−1k.\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/k1/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+1n+1 stops were the same as the times for nn 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 TnT_n in terms of Tn−1T_{n-1}, is called a recurrence relation. A natural question to ask is if we can solve this, and obtain a formula for TnT_n in terms of just nn alone. Unfortunately this recurrence relation is nonlinear due to the square root term Tn−1\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 rjr_j for a fixed number of stops.

Python #

import math

import matplotlib.pyplot as plt
import numpy as np
import scipy

def 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=2
for 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[10]

Computing T1000 #

Here is code you can use to compute and plot the T1000T_{1000} for various kk.

Python #

import math

import matplotlib.pyplot as plt
import numpy as np
import scipy

def 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 = 1000
inputvec = [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[10], Range[0.2, 1, 0.2]},
 AxesOrigin -> {1, 0}]