[Guest]

An unlimited supply of gasoline is available at one edge of a desert 800 miles wide, but there is no source on the desert itself. A truck can carry enough gasoline to go 500 miles (this will be called one "load"), and it can build up its own refueling stations at any spot along the way. These caches may be any size, and it is assumed that there is no evaporation loss. What is the minimum amount (in loads) of gasoline the truck will require in order to cross the desert? Is there a limit to the width of a desert the truck can cross?

[Guest]

When a station is built, I assume he has to fill it with the gas from his truck, making it so he has to go back to the beginning to refuel?

Build a station at mile 100.

Dump 300 miles worth of fuel each trip...after 4 loads there will be 1200 miles worth of fuel...on the 5th load take 100 miles worth(leaving 1400) for his 6th load, and go to mile 300(200 mi. from mile 100) and build a station.

Dump 100 miles worth of fuel each trip..after the 6th and 7th load he should have 200 miles worth of fuel stored at that station.

Grab the 8th load from mile 100..go to mile 300 and fill up for the 9th load..now he should have 500 miles worth of fuel to get to the 800 mile mark(the other side)....so I'll say 9 loads(thats counting topping off from one station to the next)

Wow, that was way too confusing..must be wrong somewhere..oh well.

Doing it that way, there should'nt be a maximum distance he can travel...who knows tho..

[Guest]

When a station is built, I assume he has to fill it with the gas from his truck, making it so he has to go back to the beginning to refuel?

Build a station at mile 100.

Dump 300 miles worth of fuel each trip...after 4 loads there will be 1200 miles worth of fuel...on the 5th load take 100 miles worth(leaving 1100) for his 6th load, and go to mile 300(200 mi. from mile 100) and build a station.

Dump 100 miles worth of fuel each trip..after the 6th and 7th load he should have 200 miles worth of fuel stored at that station.

Grab the 8th load from mile 100..go to mile 300 and fill up for the 9th load..now he should have 500 miles worth of fuel to get to the 800 mile mark(the other side)....so I'll say 9 loads(thats counting topping off from one station to the next)

Wow, that was way too confusing..must be wrong somewhere..oh well.

Doing it that way, there should'nt be a maximum distance he can travel...who knows tho..

EDITED INSIDE SPOILER

[Guest]

build a station at 200 miles (station 1) and 300 miles (station 2).

First 5 loads: dump 100 at first station, so now there's enough for 500 miles at station 1.

6th trip: take 500 from border, tank 100 at station 1, dump 200 at station 2 and go back to station 1; now there's 400 at station 1 and 200 at station 2.

7th trip: take the 400 from station 1, go station 2 and tank the 200, with the 500 in the truck the desert can be crossed.

[Guest]

build a station at 200 miles (station 1) and 300 miles (station 2).

First 5 loads: dump 100 at first station, so now there's enough for 500 miles at station 1.

6th trip: take 500 from border, tank 100 at station 1, dump 200 at station 2 and go back to station 1; now there's 400 at station 1 and 200 at station 2.

7th trip: take the 400 from station 1, go station 2 and tank the 200, with the 500 in the truck the desert can be crossed.

if u build a station at 200 miles and 300 miles u will able go back to a distance of 200 miles ,and u cant reach the supply

Edited June 30, 2009 by rohit_bd

[Guest]

if u build a station at 200 miles and 300 miles u will able go back to a distance of 200 miles ,and u cant reach the supply

you're right, but the first station is build during the first trip, the second station is build during the 6th trip, then it's possible again

[Guest]

The desert can be crossed in 6 loads.

3 loads from base to station 1 and back at 100 miles --- deposit 300 miles worth of fuel each time (total 900)

1 load from base to station 2 at 200 miles -- deposit 200 miles worth of fuel and go to station 1 (total at station 1 - 900; station 2 - 200)

1 load from station 1 to station 3 at 300 miles and back ---- deposit 100 miles worth of fuel (total at station 1 - 400; station 2 - 200; station 3 - 100)

Finally, fill 400 at station1, then 200 at station 2 and 100 at station 3 - have 500 at station 3 - cross the desert

Edited June 30, 2009 by DeeGee

[Guest]

1. Build station 1 at 125 mi, dropping 250 mi worth of fuel; return to HQ.
   This leaves one cache at 125 mi with 250 mi worth of fuel.
   
2. Drive to station 1, refuel; build station 2 at 300 mi dropping 150 mi worth of fuel; return to station 1, refuel; return to HQ.
   This leaves one cache at 300 mi with 150 mi worth of fuel.
   
3. Drive to station 1 at 125 mi, dropping 250 mi worth of fuel; return to HQ.
   This leaves two caches, one at 125 mi with 250 mi worth of fuel and one at 300 mi with 150 mi worth of fuel.
   
4. Drive to station 1, refuel; drive to station 2 dropping 150 mi worth of fuel; return to station 1, refuel; return to HQ.
   This leaves one cache at 300 mi with 300 mi worth of fuel.
   
5. Drive to station 2, refuel; drive to the other side of the dessert.
   

This uses 2500 mi worth of fuel.

Using this "modular" strategy (steps 1 and 3 are the same) we can cross any size desert.

I suspect this is best possible*, but too tired now to think about it.

*oops, looks like DeeGee's method is better.

Edited June 30, 2009 by manwe

[Guest]

you're right, but the first station is build during the first trip, the second station is build during the 6th trip, then it's possible again

post ur answer in steps so that it can easily understood

[Guest]

The desert can be crossed in 6 loads.

3 loads from base to station 1 and back at 100 miles --- deposit 300 miles worth of fuel each time (total 900)

3 loads +

1 load from base to station 2 at 200 miles -- deposit 200 miles worth of fuel and go to station 1 (total at station 1 - 900; station 2 - 200)

1 load +

1 load from station 1 to station 3 at 300 miles and back ---- deposit 100 miles worth of fuel (total at station 1 - 400; station 2 - 200; station 3 - 100)

1 load +

Finally, fill 400 at station1, then 200 at station 2 and 100 at station 3 - have 500 at station 3 - cross the desert

3 loads = 8 loads

I see 8 loads(noted in your spoiler)....I was counting each fill up as a load...if not then I need to revise my answer..I think your way still beats me by 1 either way tho.. edit:or maybe 2

Edited June 30, 2009 by James8421

[Guest]

build a station at 200 miles (station 1) and 300 miles (station 2).

First 5 loads: dump 100 at first station, so now there's enough for 500 miles at station 1.

6th trip: take 500 from border, tank 100 at station 1, dump 200 at station 2 and go back to station 1; now there's 400 at station 1 and 200 at station 2.

7th trip: take the 400 from station 1, go station 2 and tank the 200, with the 500 in the truck the desert can be crossed.

I think you've missed two loads as I highlighted in your spoiler.

As you and James found, I also found many ways for 9 loads solution. A lesser may exists??? I'm not sure.

There shouldn't be a distance limit, if time and fuel are unlimited. You can construct unlimited stations and fill them with unlimited fuel and reach to unlimited distance.

[Guest]

I think 5 loads is right, of course I'm not counting stops at refueling stations as loads. But using this method leaves no fuel wasted.

station 1 (s1): 125 miles out

station 2 (s2): 300 miles out

goal is to get 300 miles of fuel at s2.

first: s1 drop 250, return

second: s1 drop 250, return (s1 at 500)

third: s1 take 125 (s1 at 375 now), drop 150 at s2, return to s1 take 125 and return (s1 at 250)

fourth: s1 take 125 (s1 at 125) drop 150 at s2 (s2 at 300) return to s1 take 125 and return (s1 at 0).

fifth: station 2 take 300 (leaving s2 at 0) with 500 miles of fuel in tank, cross dessert.

5 steps, used 2500 miles of fuel. Can anybody get 4?

[Guest]

I think 5 loads is right, of course I'm not counting stops at refueling stations as loads. But using this method leaves no fuel wasted.

station 1 (s1): 125 miles out

station 2 (s2): 300 miles out

goal is to get 300 miles of fuel at s2.

first: s1 drop 250, return

second: s1 drop 250, return (s1 at 500)

third: s1 take 125 (s1 at 375 now), drop 150 at s2, return to s1 take 125 and return (s1 at 250)

fourth: s1 take 125 (s1 at 125) drop 150 at s2 (s2 at 300) return to s1 take 125 and return (s1 at 0).

fifth: station 2 take 300 (leaving s2 at 0) with 500 miles of fuel in tank, cross dessert.

5 steps, used 2500 miles of fuel. Can anybody get 4?

if u took 125 from s1 (third) u will be left with gasoline for 250 mile, the how did u goto s2 and dropped 150.

Edited June 30, 2009 by rohit_bd

[Guest]

Hey, it looks to me like DeeGee's method uses 2000 mi worth of fuel (four loads). Here it is:

1. Build station 1 at 100 mi, dropping 300 mi worth of fuel; return to HQ, refuel.
   
2. Drive to station 1 at 100 mi, dropping 300 mi worth of fuel; return to HQ, refuel.
   This leaves one cache at 100 mi with 600 mi worth of fuel.
   
3. Drive to station 1 at 100 mi, dropping 300 mi worth of fuel; return to HQ,refuel.
   This leaves one cache at 100 mi with 900 mi worth of fuel.
   *After this point we never visit HQ any more, so we only use four loads of fuel (the initial load plus the 3 refuels at HQ).
   
4. Drive to station 2 at 200 mi, dropping 200 mi worth of fuel; return to station 1, refuel;
   This leaves two caches: one at 100 mi with 400 mi worth of fuel and one at 200 mi with 200 mi worth of fuel.
   
5. Drive to station 3 at 300 mi, dropping 200 mi worth of fuel; return to station 2 at 200 mi, refuel, but only to 1/5 capacity (100 mi worth in the tank); return to station 1 at 100 mi, refuel (only to 4/5 capacity).
   This leaves two caches: one at 200 mi with 100 mi of fuel and one at 300 mi with 200 mi worth of fuel.
   
6. Drive to station 2 at 200 mi, refuel (up to 4/5 cap.); Drive to station 3 at 300 mi, refuel (up to capacity); Drive to the other side of the desert.
   

I modified his method slightly so show that you don't have to refill the tank to capacity whenever possible to achieve the best result. That's kinda counterintuitive to me.

[Prof. Templeton]

Hey, it looks to me like DeeGee's method uses 2000 mi worth of fuel (four loads). Here it is:

1. Build station 1 at 100 mi, dropping 300 mi worth of fuel; return to HQ, refuel.
   
2. Drive to station 1 at 100 mi, dropping 300 mi worth of fuel; return to HQ, refuel.
   This leaves one cache at 100 mi with 600 mi worth of fuel.
   
3. Drive to station 1 at 100 mi, dropping 300 mi worth of fuel; return to HQ,refuel.
   This leaves one cache at 100 mi with 900 mi worth of fuel.
   *After this point we never visit HQ any more, so we only use four loads of fuel (the initial load plus the 3 refuels at HQ).
   
4. Drive to station 2 at 200 mi, dropping 200 mi worth of fuel; return to station 1, refuel;
   This leaves two caches: one at 100 mi with 400 mi worth of fuel and one at 200 mi with 200 mi worth of fuel.
   
5. Drive to station 3 at 300 mi, dropping 200 mi worth of fuel; return to station 2 at 200 mi, refuel, but only to 1/5 capacity (100 mi worth in the tank); return to station 1 at 100 mi, refuel (only to 4/5 capacity).
   This leaves two caches: one at 200 mi with 100 mi of fuel and one at 300 mi with 200 mi worth of fuel.
   
6. Drive to station 2 at 200 mi, refuel (up to 4/5 cap.); Drive to station 3 at 300 mi, refuel (up to capacity); Drive to the other side of the desert.
   

I modified his method slightly so show that you don't have to refill the tank to capacity whenever possible to achieve the best result. That's kinda counterintuitive to me.

I think there is a problem between steps 3 and 4. You seem to be dropping 300 gallons and also taking it with you to station 2 at the same time. It looks like one more trip to base is needed.

Edited June 30, 2009 by Prof. Templeton

[Guest]

I think there is a problem between steps 3 and 4. You seem to be dropping 300 gallons and also taking it with you to station 2 at the same time. It looks like one more trip to base is needed.

4 fillups at base for a total of 2000 miles travelled.

(asterisks mark fillups at base)

Base 100 mi S1 100 mi S2 100mi S3 500 mi Dest

*Start - T = 500

Drive to station 1. T=400.

Drop 300. T=100, S1=300.

Drive to Base. T=0, S1=300.

*Fill up. T=500, S1=300

Drive to station 1. T=400, S1=300.

Drop 300. T=100, S1=600

Drive back to base. T=0, S1=600

*Fill up. T=500, S1=600

Drive to station 1. T=400, S1=600

Drop 300. T=100,S1=900

Drive to base. T=0, S1=900

*Fill up (last time) T=500, S1=900

Drive to station 2. T=300, S1=900.

Drop 200, T=100, S1=900, S2=200

Drive to station 1. T=0, S1=900, S2=200

Fill up. T=500, S1=400, S2=200.

Drive to station 2. T=400, S1=400, S2=200.

Get 100. T=500, S1=400, S2=100

Drive to station 3. T=400, S1=400, S2=100.

Drop 300. T=100, S1=400, S2=100, S3=300

Drive to station 2. T=0, S1=400, S2=100, S3=300

Get 100. T=100, S1=400, S2=0, S3=300

Drive to station 1. T=0, S1=400, S3=300.

Get 400. T=400, S1=0, S3=300.

Drive to station 3. T=200, S300

Get 300. T=500

Drive to goal.

Edited June 30, 2009 by tpaxatb

[Guest]

Start -- Base Fill-Up #1: T = 500

Drive to Station 1 (133⅓-Mile Station): T=366⅔

Drop 233⅓: T=133⅓, S1=233⅓

Drive to Base: T=0, S1=233⅓

Base Fill-Up #2: T=500, S1=233⅓

Drive to Station 1: T=366⅔, S1=233⅓

Drop 233⅓: T=133⅓, S1=466⅔

Drive back to base: T=0, S1=466⅔

Base Fill-Up #3: T=500, S1=466⅔

Drive to Station 1: T=366⅔, S1=466⅔

Drop 233⅓: T=133⅓, S1=700

Drive back to base: T=0, S1=700

Partial (13/15ths) Base Fill-Up #4: T=433⅓, S1=700

Drive to Station 1: T=300, S1=700

Station 1 Fill-Up: T=500, S1=500

Drive to Station 2 (300-Mile Station): T=333⅓, S1=500

Drop 166⅔: T=166⅔, S1=500, S2=166⅔

Drive to Station 1: T=0, S1=500, S2=166⅔

Station 1 Fill-Up: T=500, S1=0, S2=166⅔

Drive to Station 2: T=333⅓, S1=0, S2=166⅔

Station 2 Fill-Up: T=500, S1=0, S2=0

Drive to Goal: T=0, S1=0, S2=0

If we were only going 766⅔ miles instead of 800, we could actually make it in three full tanks.

Edited June 30, 2009 by M. Dale

[Guest]

Spoiler for And I don't feel like proving this, but it looks like the maximum distance one can go on n fill-ups is:

500/1 + 500/3 + 500/5 + ... + 500/(2n-1)

Edited June 30, 2009 by M. Dale

[Guest]

I think i've got it

It can be done in 4 loads:

Load #1:

Go forth 150 mi. T=350

Make station 1, drop 200 mi worth of fuel. T=150; S1=200;

Note: Station 1 is located 150 mi from base.

Go back 150 mi (to base). T=0; S1=200;

Load #2:

Go forth 150 mi (to station 1). T=350; S1=200;

Drop 200 mi worth of fuel on station 1. T=150; S1=400;

Go back 150 mi (to base). T=0; S1=400;

Load #3:

Go forth 150 mi (to station 1). T=350; S1=400;

Drop 200 mi worth of fuel on station 1. T=150; S1=600

Go back 150 mi (to base). T=0; S1=600;

Load #4:

Go forth 150 mi (to station 1). T=350; S1=600;

Refuel (150 mi worth of fuel). T=500; S1=450;

Go forth 150 mi. T=350; S1=450;

Make station 2, drop 200 mi worth of fuel. T=150; S1=450; S2=200;

Note: Station 2 is located 300 mi from base.

Go back 150 mi (to station 1). T=0; S1=450; S2=200;

Refuel 450 mi worth of fuel. T=450; S1=0; S2=200;

Go forth 150 mi (to station 2). T=300; S1=0; S2=200;

Refuel 200 mi worth of fuel. T=500; S1=0; S2=200;

Go forth 500 mi.

[Guest]

I think my 6 step method works out. Tell me if my measurements are wrong. I spent the last few hours working and reworking this.

In incrememts of 125 miles you will make the trip in 6 loads. *125* means the mile marker for 125 miles into the desert. I have a picture I will post in a bit.

1. At *125* and *250*, build stations, then return.

2. Go to *125*, deposit 250 gallons and return.

3. Go to *125*, deposit 250 gallons and return.

4. Go to *125*, withdraw 125 gallons and go to *250*. Deposit 250 gallons at *250* and return to *125*. Withraw 125 gallons from *125* and return to base.

5. Go to *125*, withdraw 125 gallons and go to *250*. Withdraw 125 gallons from *250* and go to *375*. Build a station and deposit 125 gallons. Go to *125*, withdraw 125 gallons and return to base.

6. Go to *125* and withdraw 125 gallons. Go to *250* and withdraw 125 gallons. Go to *375* and withdraw 125 gallons. Drive on through to the 800 mark and beyond.