Desert and Truck

A variant of an old problem. You have a pickup truck with room for two containers of gasoline. The gas tank of your truck has room for a trip of 600 miles, each container for 300 miles. At source town you have an infinite amount of duel available. How much fuel do you need to get to across a desert 3,000 miles wide?

Originally posted by talzamir
A variant of an old problem. You have a pickup truck with room for two containers of gasoline. The gas tank of your truck has room for a trip of 600 miles, each container for 300 miles. At source town you have an infinite amount of duel available. How much fuel do you need to get to across a desert 3,000 miles wide?

Reveal Hidden Content

If we label the source town = A, and label the point 300 miles out = B, 600 miles out = C and so on such that the destination town (3000 miles away) = K.

Assuming we want to deliver 1200me (mile equivalents of fuel) to point G then the fuel required to do this is 76,800me (or 256 containers worth of fuel). You can deliver 600me a distance of 300 miles at the cost of tank of gas - in other words you use half the fuel when delivering containers fuel a distance of 300 miles. I believe the formula is 1200*2^(n-4) where n is the total number of 300me intervals (being 10 and we deduct 4 intervals which we can do on a full tank carrying 2 containers) and 1200 is 4*300 (300 being the distance travelled using a container of fuel, and 4 being the number of intervals over which you can make a mad dash for the finish arriving at point K as you run out of fuel).

I just ran this though a simulator and it seems to work.

Interesting follow-up question for someone : assuming a second truck follows the first truck (using any fuel that may have been left behind by the first truck) - what is the minimum amount of fuel the second truck needs to pick up from the same source in order to cross the same desert after the first truck? (Edit: assume the 2nd truck does not have the same carrying capacity constraint as the 1st truck)

I've been thinking about this. Given there is some fuel left behind per my previous post, I'm not sure this is the *most* efficient method possible........?

I think I may have summed too many containers from my work.

You need 4 containers of fuel at point G as defined by andrew93 in order to make it to point K.

Starting the trunk at point F, in order to deliver those 4 containers and get the trunk to point G, you need 7 (4 + 3).

At point E: 14 (3*4 + 2)
At point D: 27 (6 * 4 + 3)
At point C: 54 (13 * 4 + 2)
At point B: 107 (26 * 4 + 3)
At point A: 214 (53 * 4 + 2)

So you need a total of 214 containers to get the truck to point K, not 427, which I incorrectly summed up all of those numbers to get.

This method leaves no fuel behind.

The way I was thinking of also leaves nothing in the desert.. well, except for empty barrels I suppose. That method was based on the idea of getting 600 me of gasoline at 2400 miles, 1800 miles, 1200 miles, and 600 miles, then going the distance, refueling four times along the way. As for all of us, building the depots looks like the Tower of Hanoi game.

@talzamir : I have worked on the assumption the drop off points are in multiples of 300 miles, given you cannot deliver fuel more than 300 miles without consuming some of the fuel you have already brought out into the desert - which I believe (intuitively rather than mathematically) will be less efficient. For example, you cannot build a depot at the 2400 mile mark, without first storing fuel at the 2700 mile mark (and using some of it in the process).

@forkedknight : I agree there is a more efficient method than the one I posted above. I have re-visited and I agree you need 7 at point F, but I believe you only need :
~ 12 at point E;
~ 23 at point D;
~ 44 at point C;
~ 87 at point B, and
~ 172 at point A.

This leaves no containers of fuel behind. To get 7 to point F:
1) we use 4 fuel to deliver 2 to F and return to E
2) we use 4 fuel to deliver 2 to F and return to E
3) we use 4 fuel to deliver 2 to F and remain at F with 1 container worth of fuel in the tank
Total fuel at point F = 7
Total fuel at point E = 12

To get 12 to point E:
1) we use 4 fuel to deliver 2 to E and return to D (we do this 5 times)
6) we use 3 fuel to deliver 2 to E and remain at E with 0 fuel in the tank.
Total fuel at point E = 12
Total fuel at point D = 23

.....and so on for each point......

The number required flips from odd to even at each point. Working backwards (i.e. from point F to point A), the fuel required at point n-1 (assuming we want to get fuel to point n) is:

if fuel(n) is even : fuel(n-1) = (fuel(n) * 2) - 1
if fuel(n) is odd : fuel(n-1) = (fuel(n) - 1) * 2

There may be a simpler way to express this, but this is what I came up for the moment.

Andrew

P.S. This assumes a process of stock-piling fuel at 300 mile intervals and only moving on to the next point once you have a enough fuel to complete the entire journey. There may be another method for delivering the minimum fuel necessary to complete a single journey as post by talzamir but I haven't looked at that method yet.

My method was like this..

Start at point A
fuel up, load 2 tanks
A -> A+300, drop 2 tanks
drive to A
fuel up, load 2 tanks
A -> A+300, fuel up from one or the canisters there
A+300 -> A+600, drop 2 tanks
A+600 -> A+300, fuel up from the remaining canister there
A+300 -> A

Each cycle converts 8 tanks at A into 2 tanks at A+600. If you're done with the depot, load up, drive 600 miles, and drop 2 canisters there, ending up with the same situation as at the start, but at 600 miles further into the desert. n repetitions mean

Consumption at zero: 8n + 4
Stock at 600: 2n + 2

Repeat the process to move fuel and finally the car from the 600 mile depot to the 1,200 mile depot, using up all the fuel from the 600-mile depot in the process. m repetitions mean

Consumption at 600 miles: 2n + 2 = 8m + 4
Stock at 1,200: 2m + 2

Repeat once more to make a deport at 1,800 miles.

Consumption at 1,200 miles: 2m + 2 = 8k + 4
Stock at 1,800: 2k + 2

Finally, build a 2-tank stock at 2,400 miles, then fuel up at 1,800 and put the last two tanks on the truck. That requires the stock at 1,800 to be

2 x 4 + 2 + 2 = 12 tanks.

Hence
2k + 2 = 12 => k = 5
2m + 2 = 8k + 4 => m = 4k + 1 = 21
2n + 2 = 8m + 4 => n = 4m + 1 = 165

And the consumption at the start
8 x 165 + 4 = 1,324 tanks.

Looks rather horrific.

Number intermediate points on the 3000-mile trip such that point 1 is 300 miles from the origin, point 2 600 miles from the origin, and so on until point 10 (which is the end point of the journey).

Starting at the origin, move 86 containers to point 1 by making 42 round trips from 0 to 1, and one final one-way trip, refilling at the origin each time. The truck delivers 86 containers to point 1 and arrives with half a tank of gas (the equivalent of one container).

Move 44 containers of gas from point 1 to point 2, refilling at point 1 each time. This requires 21 round trips and one one-way trip, and consumes 42 containers plus the one container that was left in the truck when it arrived at point 1. Of the 86 containers left at point 1, 44 move to point 2 and 86 - 44 = 42 are consumed. The truck arrives at point 2 with an empty tank.

Move 22 containers to point 3 by making 10 round trips and one one-way trip, requiring 20 containers for the round trips, one for the one-way trip, and leaving one container of gas in the gas tank. (22 + 20 + 1 + 1 = 44 tanks originally at point 3.)

Move 12 containers to point 4 by making 5 round trips and one one-way trip. The 5 round trips consume 10 containers and the container left in the truck when it arrived at point 4 lets it make the one-way trip. So of the 22 at point 4, we use 10 and move 12, arriving at point 4 with an empty tank.

Move 6 containers to point 5 by making 2 round trips and one one-way, using 6 containers and arriving at point 5 with one container left in the truck's gas tank. So we moved 6 of the 12 containers, and used the other 6.

Move 4 containers to point 6 by making one round-trip and a one-way trip, consuming 2 containers plus the one that had been in the truck's gas tank. The truck arrives at point 6 with an empty tank.

The remaining four tanks will get the truck from point 6 to point 10, consuming all the remaining fuel.

In order to deliver 86 containers to point 1, the truck was filled with the equivalend of 86 containers of fuel. So the total fuel consumed is 86 + 86 = 172 containers.

Nice work - I came up with the identical solution above that requires 172 containers.

Can anyone come up with anything better?

Excellent scheme! think it is likely to be the best because the truck does no "long" trips, so it probably carries the most barrels per tank of fuel burned.