Crossing the Desert
An unlimited supply of gasoline is available at the edge of a desert 800 miles wide, but there is no gasoline in the desert. A truck can carry enough gasoline to go 500 miles (this amount will be called one load), and it can build up its own refueling stations at any point along the way. These caches can be any size and it is given that there will be 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 size of a desert the truck can cross?
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 size of a desert the truck can cross?
posted by Zaux at
5:01 AM
10 Comments:
Going to spend Christmas day with family ... and I wish all you fellow puzzlers a very Merry Christmas.
Zaux
Crossing the Desert
Call the amount taken from the home base gas station S
Each time the truck visits S it will pick up a full tank of gas (500miles worth)
Call the distance from S to point A , D1
At A there is a tank with TA amount of gas
Call the distance from point A to point B , D2
At B there is a tank with TB amount of gas
Call the distance from point B to the final destination D3
D1+D2+D3=0
If the truck drives from S with a full tank to point A
It will burn up D1 fuel
leaving the truck with 500-D1 fuel
in order to return to S it must save D1 fuel
So the surplus fuel the truck may leave in TA is
500-2*D1
Repeat this NA times and the fuel in TA will be
TA=(500-2*D1)*NA
And the fuel taken from S will be
S=500*NA
Once we have built up sufficient fuel in TA we can drive the truck back and forth from A to B in order to fill the tank at TB. We fill the tank to 500 each time we return to TA.
If the truck drives from A with a full tank to point B
It will burn up D2 fuel
leaving the truck with 500-D2 fuel
in order to return to A it must save D2 fuel
So the surplus fuel the truck may leave in TB is
500-2*D2
Repeat this NB times and the fuel in TB will be
TB=(500-2*D2)*NB
And the fuel taken from TA will be
TA=500*NB
On the final journey from TB to the final destination, we fill up the truck from TB and traverse D3.
Set D3 to 500 to maximize the final journey, as this would be the most efficient method.
So we see that
TB must be >= D3 and ideally we waste no fuel in TB, thus we set TB=D3
(500-2*D2)*NB=500
-2*D2*NB+500*NB=500
D2*NB=(500-500*NB )/-2
D2=250*(1-1/NB)
NB must be an integer value >=1
Minimizing NB would be ideal
if NB=1 D2=0
D2 cannot be 0 thus NB >1
if NB=2 D2=125
fuel we use from TA=500*NB=1000
fuel we put in tank at TA is (500-2*D1)*NA
(500-2*D1)*NA > 500*NB
D1=800-500-125=175
(500-2*175)*NA>500*2
150*NA > 1000
NA > 1000/150= 6.66666
NA = 7
The fuel taken from S will be
S=500*NA= 500*7
S=3500 miles
3500 miles = 7 loads
Answer:
7 loads
Given a waypoint d away, we demonstrated that the tank will accumulate
(500-2*d)*N of gasoline. With an unlimited supply of gas, and an infinite number of iterations a truck could deposit an infinite supply of gas at the waypoint.
(lim N-> inf. for (500-2d)*N = inf.)
As such, the waypoint for all intents and purposes is identical to the starting point except it is d closer to the destination. Thus we can simply repeat the process, until the desired distance is traversed i.e. there is no limit to the size of desert that the truck can cross.
Cam
I agree with Cam for the size of the desert.
However, if I read Cams solution correctly, then he is going the full 500 miles, there and back, leaving no fuel for the way station?
To do the last 500 miles, you need to have got 500 gals of fuel 300 miles from the start point. I haven't checked if the rest is optimal. To get 500 gals 300 miles out, I guess that you will have got 1000 gals to x before the 300 mile point and that will have taken 2 out and 1 return from the previous dump. So x is given by, 1000 = 500+3x => x = 166.66666.... So the previous dump is 300 - 166.6666.. = 133.3333...miles from the start. You can get 1000 gals to that dump if you start with 1500 gals a distance y nearer to the start point. That needs 3 out and 2 return trips: 1500 = 1000 + 5y => y = 100 miles. So the previous dump would be 33.3333... miles from the start. To deliver 1500 gals to the 33.3333... mile out dump require 4 out and 3 return trips. The first 3 round trips will deliver 1300 gals (that's 1500 -6*33.3333..) to the 33.333... mile point, the last outward trip only requires picking up 233.3333 gals.
So my answer is 1733.3333/500 = 3.46666666... loads.
The maximum crossing width for N dumps is: 500(1+1/3+1/5+...1/(2N+1)) {N = 0,1,2,3,...}. The number of loads = N+1.
The series 1 + 1/3 + 1/5 + 1/7 + ... is divergent (see Hardy and Wright, 1968, Theorem 19). So the maximum width of the desert that can be crossed is not limited by fuel logistics.
Chris .... nice work ... that is correct ... 3.46 loads. And you are also right in that there is no limit to the desert size.
"I knew that.", (S, 2009).
I note that Hardy and Wright's proof is surprisingly heavy going.
So here's my proof:
1 + 1/3 + 1/5 + 1/7 ... > 1/2 +1/4 + 1/6 + 1/8 + ...
RHS = (1/2)*(1 + 1/2 + 1/3 + 1/4 + ...)
The last factor is the well know divergent harmonic series. So the LHS diverges also.
Nice work Chris. I assumed, incorrectly, that adding additional way stations would be less efficient. My intuition failed me.
Cam
Hi Cam. I found my intuition surprisingly stretched as well. It's curious when it all looks so simple.
I can only say that I'm pretty sure that the most efficient procedure involves consuming 500 gallons per way station and that you must do that with the minimum numbers of out and backs between each station. I.e. I am confident that I have actually got the optimum approach.
Also, it was nice beating you for once ;)
Post a Comment
Links to this post:
Create a Link
<< Home