*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.