Game Design Maths Problem

On the subreddit r/askmath a user asked about a problem which had come up while designing a game. If you have ever played an idler game you'll be familiar with the logic. (While if you haven't played an idler game before then I heavily advise that this revision filled period just before your exams is not the time to find out. Go and do a past paper!) Here's the set up:

You start with £0 and your goal is to get £100. Your initial income is £1/second which flows in continuously rather than as a lump sum. At any point you may spend all £n of your money to upgrade your income to £n/second leaving you with a bigger income but essentially restarting you down to having no money again. You can do this as many times as you want and there is no requirement that n is rational. How can you get to £100 in the shortest time?

Waiting 100 seconds and never cashing in would get you there, but how about if we cash in just once? Waiting 2 seconds and upgrading would reset you but with double the rate of gain. After that it would only take an additional 50 seconds to get £100, making a total of 52 seconds.

How about waiting for an income of 3 seconds instead? This will take 3+100/3=36.33... seconds which is an improvement. 4 seconds wait gives 29 seconds in total, 5 gives 25, 6 gives 22.7, 7 gives 21.3,  8 gives 20.5, 9 gives 20.1, 10 gives 20 before finally 11 gives 20.1 which is longer. So allowed only one upgrade we should wait 10 seconds and then upgrade and ride it out.

In general the time t=x+100/x for x seconds. Note we could have got to the above result by finding the minimum value of t by differentiating and finding the turning point:

Since x has to be positive, x=10 is minimal as before for a total time of 20 seconds.

How about with 2 updates? Can we beat 20 seconds? Well the equivalent formula for upgrading at time x then time y is t=x+y/x+100/y. This has two variables which we can fiddle with. My way in was to first try a grid of different numbers for x and y. Here's a Google Sheet with a table of results. I've highlighted the best result in 5 which dips just under 14 seconds by upgrading to 5 and then 22. However this is just for integer amounts; it would be nice to get the actually optimum.

If you look at the results and picture each number as the height of the point on a grid. You can picture it as a 3D surface. The whole thing is like a big crater. If we found the gradient with respect to x as why kept y constant then we could find the stationary points in that direction. Similarly we could find the gradient with respect to y as we hold x constant. If there is a point where both of these things are minimal then that should be the point that we want.

These are called partial derivatives. We signify them with curly ds. You just have to pretend that all other variables are just constants.

By putting these derivatives equal to zero we get two linear equations. Let's solve them:

So we upgrade at the cube route of 100 then the square of that. It is like we have split the 100 into 3 equal pieces but in a multiplicative sort of way rather than an additive sort of way. This is the sort of thing that logs were built for. Overall we get t=13.9247665...seconds. This fits in with our integer based raw data above.

3 upgrades? It's basically the same thing:

Notice that the first upgrade is the 4th root of 100 which follows the general pattern. Working out the time gives root10+root10+root10+root10=12.64911064...seconds.

The general case is the same although it gets a bit messy. For n upgrades it turns out that you need the first upgrade at the (n+1)th root of 100 and then each subsequent upgrade at each power of the first upgrade value.

This results in a total time of (n+1)100^(1/(n+1)).

Time to go for infinite upgrades? What is the minimum value of the above function or does it approach some limit? Differentiating it (taking logs first) and setting it equal to 0 we get n=ln(100)-1=3.6...  but that is nonsensical because we need n to be integer. Trying in 3 and 4, we get 12.65 (as above) or 12.56. By 5 upgrades it starts going back up to 12.93 and it only gets bigger from there. Long term n upgrades results in just over n seconds as n gets large.

Done. 12.56 seconds is optimum.