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

- Thread starter uzurpatorul
- Start date

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

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.

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.

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.

You have used: (150+500+500)/500=2.3 loads.

But it's still not the solution.

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.

We can work backwards in this fashion to find there are 3 refueling stations. The one-load station is 300 miles into the desert. The two-load station is 500/3 miles earlier at the 400/3 mile marker. The three-load station is 100 miles before that at the 100/3 mile marker. We will use 7 trips from the edge of the desert to the three-load station to deposit the three loads of gas there. We will use 5 trips between the three-load station to the two-load station to pick up three loads of gas and drop off two loads. Etc. So the total milage is 7 * 100/3 + 5 * 100 + 3 * 500 / 3 + 500 == 700/3 + 500 + 500 + 500 == 1500 + 700/3. This is 3 + 7/15 loads of gas to cross the desert. 7/15 is 0.466, so the answer to be entered is 3.46 (truncated to 2 decimal points).

I agree that there should be a constraint of scarce resources in the question.