Welcome to NRICH.

 
Strategic placing of fuel reserves
By Cosmin Negruseri on Saturday, September 07, 2002 - 12:03 pm:

You have to travel N kilometers with a jeep which has a reservoir capacity of M litres and the jeep consumes one litre every kilometer. In the start point there is a unlimited amount of fuel.You can leave reserves of fuel on the road and use them later. The task asks what is the minimum amount of fuel that can be used.

By Ngoc Tran on Monday, September 09, 2002 - 07:13 am:

Let's call the distance between the 0 point and reserve 1 is A. our aim is to:
1/ make A as large as possible
2/ make the fuel in reserve 1 is equal to the fuel spent by the jeep when traveling from 0 to A (can you see why?)
3/ we also need to remember that at the first time to "drop" the fuel at reserve 1, the jeep need fuel to return to.

--> we have the formula for the distance between 2 reserves: (called this distance x, and K is the distance between the previous reserve and the origin 0).

x = (M - K)/3 (equa.1)

From that, we can see that:
The distance that jeep can travel before run out of fuel totally = M + k (equa. 2)

From equa. 1, it's obvious that x needs to be postive, that is M is always greater than K. Combine this with equa. 2, we can see that:

If N > 2M then the jeep would NEVER be able to travel to N.
If M < N < 2M, then the formula would be:

N <= M + k
where
K = (M - x1)/3 + (M - (x1 + (M - x1)/3))/3 ... and so on
where
x1 is the distance between the first reserve and the origin (which is 1/3M - as we calculated above);

The above formula is just the "plain" formula, which tell you about the number of reserves that you got to put - NOT the distance the jeep travels. If you think about it, then after journey 1 - which create reserve 1, the jeep need to go back, and start journey 2 to create reserve 2, which will use all the fuel at reserve 1. And then the jeep got to fill-in reserve 1 again, which would take another journey.

I hope you guys can figure out the distance formula, because it's just the matter of time,

Ngoc,

By Edvin Deadman on Monday, September 09, 2002 - 10:24 am:

I've done it a slightly different way. I also use the fraction M/3 for the 'reserve points' but I figured it doesn't matter if N>2M because the jeep can transport as much fuel as it wants to reserve1 and therefore as much as it wants from reserve1 to reserve2 and so on.

Instead I worked backwards:
we need a reserve of M at a distance M from the end (call this reserve k). Before this, we need reserves of fuel every M/3 distance. To transport a reserve of M from reserve k-1 to reserve k we need 8M/3 at reserve k-1 and by a similar argument we need 23M/3 at reserve k-2 (remember: each time we go forwards a distance M/3 then leave M/3 in fuel then go back, except for the last time when we don't go back)

We now have a series in which the nth term is:
M(5×3x + 1)/6 (that's if we take reserve k to be therm 0). We want the 3(N-M)/M th term so plug this in in place of x and we get our equation. The equation tells us how much fuel is used, but since fuel consumption = 1 it also tells us the distance travelled.
Well that's moreorless how I did it (I haven't explained it in particularly great detail, sorry!), perhaps it's not that different from Ngoc's method after all...
Edvin