Decreasing function with a target integral?

Question

Problem Definition: I have a certain amount (S) of time that I can use over a fixed number of turns (T) in a game. I want to invest more of my time in the early turns, but still have a little time left for my last turn. As an example, if S = 55 and T = 10 one solution would be:

turn 1: 10

turn 2: 9

turn 3: 8

...

turn 8: 3

turn 9: 2

turn 10: 1

Written another way, I could say that f(x) = 11-x, with f(x) being the amount of seconds I used and x being the current turn.

The amount of time used decreases linearly in this case, but that is not a requirement. The only requirement is that I have a function that decreases the amount of time used each turn, but uses all of the time in the allotted number of turns. If it makes it easier, I can make S and T definite constants (in practice I'll have 10000 seconds to use in 100 turns), but it seems to me that this should be able to be solved symbolically.

My Best Attempts: I tried a strategy of looking at how much time I have left at the present turn, and taking an increasing percentage of that time. The first turn I had 10000 seconds, and I used 1% of that, 100 seconds. The second turn I had 9900 seconds remaining, and I used 2% of that, or 198 seconds. I continued till the 100th turn where I used 100% of my remaining time. This tactic was waaaay off the mark. I'm embarrassed I went off the rails like that.

My most sound approach was an attempt to use calculus. I was pretty good at calculus 10 years ago, and I doubt this would have given me a problem then, but it isn't working for me now. I decided I could take any decreasing function, such as 1/x, and then scale it to suit my purposes. Let F(x) be the integral of f(x). The area under the curve f(x) from x = 1 to x = 100 should be able to be calculated using F(100)-F(1). If I have some scaling (K) factor to scale this to my desired value,

K*(F(100)-F(1)) = S

so

K = S/(F(100)-F(1))

OK, so I have a formula to find a constant that will scale the area under my given curve to be equal to my desired total value. If I go back and multiply my original function by this scaling factor I should have my desired function. I.E., if I evaluate K*(f(1)+f(2)+f(3)...f(100)) that should equal S. The thing is, it didn't work, and I don't know why. I used f(x) = 1/x, F(x) = ln(x), S = 10000, and T = 100.

S*f(x)/(F(100)-F(1))

10000*(1/x)/(ln(100) - ln(1))

10000/(4.6*x)

That gave me:

turn 1: 2174

turn 2: 1087

turn 3: 725

...

turn 100: 22

The problem here is that when I add up all the time I used in all those turns it comes out to 11277!

I've beaten my head against this all day. Please help!

Answer 1

In your first approach, you shouldn't use $1\%$ as first step and $2\%$ as second step, since this is usually not a decreasing step. I don't see directly how to improve this since always taking $x\%$ is not going to work as well.

In your second approach, the problem comes from here $$ \int_1^{100} \frac{1}{x}\,\mathrm{d} x - \sum_{i=1}^{100} \frac{1}{i} \approx 0.58. $$ And this scales up to the error of $1277$ in your case.

A fix for this would be to scale with $\sum_{i=1}^{100} 1/i$ instead of $\log(100)$. However, we don't have a closed form expression for this summation (but you can just put it into your code and calculate it).