# Crossing the desert

#### uzurpatorul

An unlimited supply of gasoline is available at one edge of a desert 800 miles wide, but there is no source in the desert itself. A truck can carry enough gasoline to go 500 miles (this is called the "load"), and it can build its own refueling stations at any spot along the way.

What is the minimum amount of gasoline (in loads) the truck will require in order to cross the desert?

http://www.projecteureka.org/problem/question/97 - you can verify your solution here

#### coax

This is an intriguing problem. Has anyone got the right answer yet? 4.6 loads is the best I can do and that was not correct.

First trip:
I loaded up 450 miles worth 9/10th of a load. Travelled 150 miles dropped off 150 miles worth of fuel and then drove back 150 miles.

Second trip:
as first trip

Third trip:
as first trip again, so that there are three loads of 150 miles worth of fuel at 150 miles into the desert. We have used 3 times 9/10 loads so far, which is 2.7 loads.

Fourth trip:
On this trip we can use two of the three 150 miles worth of fuel stuck out 150 miles into the desert, in order to drop off 150 miles worth of fuel at 300 miles into the desert. After getting back we have 150 miles worth of fuel at 150 miles into the desert and 150 miles worth of fuel 300 miles into the desert.

Fifth and final trip:
On all the previous trips we only used 9/10th of a load each time, on this trip we use a full load. After 150 miles into the desert we pick up the 150 miles worth of fuel, giving us a full load on board. At 300 miles into the desert we pick up the other 150 miles worth of fuel, giving us a full load on board again and with 500 miles left to go we can make it over to the other side. We have used 9/10 + 9/10 + 9/10 + 9/10 + 1 = 4.6 loads of fuel.

But 4.6 is not the answer they are looking for.

#### coax

By abandoning two vehicles I can get the answer down to 2.4 but this is the wrong answer too.

Vehicle 1 with a full load(500) drives out 300 miles into the desert and stays there with 200 miles worth of fuel.

Vehicle 2 with 200 miles worth of fuel drives 100 miles into the desert and stays there with 100 miles worth of fuel.

Vehicle 3 with a full load(500) can then drive 800 miles across the desert picking up 100 miles worth of fuel at 100 miles into the desert and then picking up 200 miles worth of fuel at 300 miles into the desert. At this point giving vehicle 3 a full load(500) to travel the rest of the 500 miles to the other side of the desert. Hopefully after remembering to pick up the drivers of vehicles 1 and 2.

By abandoning the two vehicles I get the answer down to:

(200 + 500 + 500)/500 = 2.4

But this answer is also wrong.

#### Jeranimo

I can even get it down to 2.3 loads:

Truck 1:
With fuel for 150 miles, drive 50 miles into the desert. (Then you have still enough fuel for 100 miles)

Truck 2:
With full load drive 50 miles into the desert and pick up fuel for 50 miles. Then drive another 250 miles into the desert. (Then you have still enough fuel for 250 miles)

Truck 3:
With full load drive into the desert and pick up all the fuel still in the trucks. Then you can make it to the other side.

But it's still not the solution.

#### cesium62

I'm not convinced that the test answer form knows the right answer.

Clearly there is only one truck and the intent is that the truck drive gasoline out to refueling stations, drive back and get more gas, and drive out to refueling stations again.

Given a set of refueling stations, for example A, B, and C; it doesn't matter if the truck first transfers all gas possible from A to B and then from B to C or if it sometimes goes from A through B to C and back to A. Basically, given an optimal driving schedule, we can reorder the schedule to take all the out-and-back trips that occur from a station nearer the starting edge of the desert before we perform trips further from the starting edge.

Working backwards, we need 1 load of gas at mile marker 300 in order to reach the other side. To get 1 load at mile marker 300, we will need 2 loads of gas at a station earlier. To transfer 1 load of gas to mile marker 300, we will start with a full load at the way-station, drive out to marker 300 and dump as much gas as we can, and then drive back to the way-station. Here we will fill up a second time, drive out to mile marker 300 and dump our gas into the way station. So there are 3 trips between the station at mile marker 300 and the previous station. These three trips will consume one load of gas, so the way-station is 1/3rd of a tank (500/3 miles) away from mile marker 300.

It's going to take 3 trips to move gas from the way-station to mile marker 300. If it takes more trips, we moved too much gas too far out into the desert. The way-station will have 2 loads of gas. If it has more gas, we moved the gas too far. If it has less gas, we aren't going to transport the gas efficiently; instead of using 1 tank of gas to transfer a tank a distance of 1/3rd of a tank, we will use 1 tank of gas to transfer less gas that distance.

#### John Wilmot

I haven't posted my answer but your algebraic proof seems reasonable. I worked it forward and reasoned that the loads should be carried forward as far as is most efficient, with allowing enough fuel to return to the stockpiles. Thus, 3.6 loads, including going out 200 miles, then the final 100 miles with enough to get to the end. I think that I'm slightly high in the rounding.
I agree that there should be a constraint of scarce resources in the question.

#### skipjack

Forum Staff
There's only one truck. The link seems to know the answer. The responses above suggest that the appropriate strategy isn't particularly obvious, so maybe it's worth solving a simpler problem first.

#### mrtwhs

This problem was first posed by Nathan Fine in 1947. You can google "the jeep problem" to see a discussion. The solution involves the harmonic series.

#### topsquark

Math Team
And don't forget the horse. You know the one? The one with no name?

-Dan