Minimum Number of Trips

Date: 07/01/2001 at 15:58:54
From: B. Hastings
Subject: Minimum number of trips puzzle

Hello, 

The problem is that of a fully laden lorry that can carry fuel and 
supplies for a trip into the desert of up to 400 miles. The base camp
on the edge of the desert has an unlimited amount of fuel and 
supplies. By setting up strategic supply dumps along the proposed 
route, it is possible to travel more than 200 miles into the desert 
and return. How many trips would be needed to penetrate 600 miles and 
back? (Note: return required.)

My son is in Year 8 in the UK, and is 13 years old.  He used trial and 
error, and found a very acceptable answer.

I enjoy puzzles, and felt sure there must be a formula, with the 
distance between supply dumps as a variable, to calculate the minimum 
number of journeys and/or the minimum distance travelled (i.e. fuel 
consumption). Starting at the most distant point, there must be a 
relation between the distance between successive supply dumps and the 
amount of fuel to be dumped there using a geometric series. When I had 
solved the basic puzzle, I intended to extend the solution to a 
variable lorry capacity and a variable end point, but I couldn't even 
solve the initial problem. I look forward your reply with 
anticipation.

Barbara Hastings.

Date: 07/02/2001 at 16:33:55
From: Doctor Jaffee
Subject: Re: Minimum number of trips puzzle

Hi Barbara,

Let's assume that 1 pound of fuel and supplies is required to travel 
1 mile. I found a solution that required a total of 11,800 pounds of 
fuel and supplies. I am curious how my solution compares with your 
son's. My solution was based on the premise that the lorry driver 
needs to deposit 800 pounds of supplies and fuel at the 400-mile 
marker. From there the driver could travel 200 miles to the edge of 
the desert, then back 200 miles where there would stil be 400 pounds 
of fuel and supplies waiting. This would be sufficient to get him 
home.

So, if he started at the base camp with 11,800 pounds, he could load 
the lorry, drive 100 miles, deposit 200 pounds of fuel and supplies, 
then drive back to base camp. He would then repeat this process until 
5900 pounds of fuel and supplies were deposited, at which time it 
would become his new base.

Then, starting from his new base he would load the lorry, drive 100 
miles deposit 200 pounds of fuel and supplies and return to base. He 
would repeat this process until a total of 3000 pounds of fuel and 
supplies were deposited and his new base camp would now be established 
at the 200-mile marker.

He would then follow the same procedure and deposit 1500 pounds of 
fuel and supplies at the 300-mile marker and finally deposit 800 
pounds of fuel and supplies at the 400-mile marker.

Now, establishing a formula is challenging. If the capacity of the 
lorry is x pounds of fuel and supplies, then you need to deposit 
x pounds at a distance of x miles from the end of the trip. However, 
in this case twice as much was required because of the looping nature 
of the trip; that is, the lorry went from the 400 miles marker to the 
end, then looped back to the 400-mile marker in one trip.

So, however many pounds of fuel and supplies are required at that last 
marker, approximately twice as much is required at the previous stop.  
That's where the complication is. In the problem your son solved, 
400 pounds of fuel and supplies is the capacity of the lorry. At 
alternate stops 100 pounds less than twice the amount required at the 
next stop must be accumulated. If the capacity of the lorry were 500 
pounds, it would work very differently.

There may be a generalized formula that will solve all problems of 
this nature, but personally I think it is easier to work it out 
logically and systematically as I have done, and as I expect your son 
did. I've enjoyed working on this problem; I found it quite 
fascinating. I hope my response has been helpful, and please write 
back if your son's solution is significantly different from mine, or 
if you want to discuss it some more.

- Doctor Jaffee, The Math Forum
  http://mathforum.org/dr.math/   

Date: 07/22/2001 at 13:14:49
From: B. Hastings
Subject: Re: Minimum number of trips puzzle

Hi, Dr Jaffee,

My son's solution was similar to yours.  Assuming 1 unit of fuel and
supplies per mile, he started from the idea that he needed 400 units 
at the 400-mile mark to reach the 600-mile point and return to the 
400-mile supply dump.

He then said that he needed to make 3 round trips from the 300-mile 
dump to the 400-mile dump, depositing 200 units per trip - since only 
making two trips would leave him stranded at the 400-mile point. To 
enable him to make three trips from 300 to 400, he said he needed to 
make seven trips from 200 to 300, fifteen trips from 100 to 200, and 
32 trips from Base to 100. This would ensure enough extra units at 
each supply dump to get him home.

His total consumption was therefore 12200 units. I thought this was a 
good solution, particularly for a 13-year-old. His teacher said the 
solution required only eleven trips, but he could not remember how she 
did it.

I think I have found a way that only takes 6400 units and 30 trips.

If the lorry makes 15 round trips from base to 100 miles depositing 
half its load each trip, there will be 3000 units at the 100-mile 
point. The lorry sets out for the 16th time from the base, and arrives 
at the 100-mile point 3/4 full. The total at the 100 m.pt. is now 
3300.

The lorry then makes 7 round trips to the 200 m.pt. using 1400 units,
depositing 1400 units and having 500 left at the 100 m. pt. It fills 
up so there are now only 100 units left at the 100 m.pt., and  sets 
out for the 8th time from the 100 m.pt.. At the 200 m.pt.,the lorry is 
3/4 full, so the total at the 200 m.pt. is now 1700 units.

The lorry makes 3 round trips to the 300 m.pt. using 600 units, 
depositing 600 units at the 300 m.pt. and leaving 500 at the 200 m.pt. 
The lorry fills up so there are now only 100 units left at the 200 
m.pt. and sets out for the 4th time from the 200 m.pt. At the 300 
m.pt. the lorry is 3/4 full, so the total at the 300 m.pt. is now 900 
units.

The lorry makes 1 round trip to the 400 m.pt. using 200 units, 
depositing 200 units at the 400 m.pt. and leaving 500 at the 300 m.pt. 
The lorry fills up so there are now only 100 units left at the 300 
m.pt.

The lorry sets out for the 2nd time to the 400 m.pt., and is still 3/4 
full when it reaches it. It takes on 100 units, completes its trip to 
the 600 m.pt. and back, and is empty when it gets back to the 400 
m.pt. It takes on 100 units and drives back to the 300 m.pt.. It takes 
on the 100 units left there, and drives to the 200 m.pt.. It takes on 
the 100 units left there, and drives back to the 100 m.pt., takes on 
100 units and drives back to base.

I tried to work with supply dumps at different distances, but couldn't 
find a better answer.

Since my solution uses exactly half the total of yours, either I have 
made an elementary error or I have saved fuel by not transporting the 
fuel necessary for the journey home to the 400 mile point. All the 
supply dumps are empty at the end of my trip.

I'm glad you found this problem as intriguing as I did. I have always
enjoyed puzzles. I think that you are probably right in saying that 
trial and error is the best way to solve  problems like this. I  just 
wondered whether my son's teacher was introducing a new topic by 
letting the children tackle a puzzle, and then explaining how it 
should be approached, but apparently not.

I hope your colleagues enjoyed this problem. Thank you for your help.
Barbara Hastings.

Date: 07/26/2001 at 20:14:45
From: Doctor Jaffee
Subject: Re: Minimum number of trips puzzle

Hi Barbara,

Bravo!  Your solution was very efficient; I went through it step by 
step and it solved the problem and used just a little more than half 
of the resources required in my solution.

Reading your solution gave me a fresh perspective on solving problems 
of this nature. I'm glad I was able to help you and I appreciate the 
new insights you have provided for me.

- Doctor Jaffee, The Math Forum
  http://mathforum.org/dr.math/