Gas truck in the desert

Is this too easy? too hard??
I notice that there are no responses to this riddle ... would someone explain why? Did I explain it poorly? Is it too hard, too easy, or what?

Thanks
Thanks for taking the trouble to respond. As a Newbie, it's appreciated.

Hey, you're right down the coast from me. I work in San Luis Obispo.

SLO
!

SLO
I guess 100 miles away is pretty close ...

I tried finding prior posts of this riddle with no luck ... any suggestions?

I even ran a version, but where it is now, who knows.

Cache and Ferry (How far can a truck go in a desert?)
A pick-up truck in the desert gets 10 miles per gallon of gas and starts
beside N 50-gallon gas drums, all full. The truck's gas tank holds 10
gallons and is empty; the truck can carry only one 50-gallon drum. How
far away from the starting point can you drive the truck?

Solution:
If the truck can siphon gas out of its tank and leave it in the cache,
the answer is:

rem = (50 n) mod 60

m = (50 n - rem) / 60

d = (1 + 1/3 + 1/5 + ... + 1/(2*m-1)) * 600 + 10 rem/(2*m+1)

A much harder problem occurs when the truck can siphon gas, but if it
does, it must siphon the gas into one of the initial barrels.

Here is a table with the amounts of gas that pass the depot sites, the
optimal locations of the depot sites, and the amounts of gas to have in
the tank as one leaves the depot sites on the outbound trip, for the
50-gallon drum, 10 MPG, 10-gallon tank, for the limited cache problem.
An optimal solution is obtained by working from the finish, back, and
using multiple trucks as detailed below. The algorithm which produced
the table is also provided.

The table is read diagonally from bottom to top beginning with the row
with the proper gas amount. Start with the trip 1 column, and fill the
tank to the designated amount, proceed to the location in the distance
column for one row up, and leave a full drum. Continue with the trip 2
column for the beginning row, fill the truck to the designated amount,
proceed up one row and over one column to the trip 1 column, fill the
tank to the designated amount, proceed to the location in the distance
column for another row up, and leave a full drum. For trips 3 to n
start in the appropriate column and move up and over until you reach
the distance column and leave the drum. If a truck arrives at a depot
site with more gas than the table amount, then no gas is added. Gas is
never removed. On return trips, the tank is only filled with enough gas
to reach the next depot site.

Since the drum and tank capacities and mileage are rational numbers,
all the table entries could be expressed precisely as rational numbers,
e.g., Row 3 is

420-10/11, 600*(1+1/3+1/5+1/7+1/9+1/11)+(600-100/11)/13, 100/11, 10, ...

The solutions all result in 6 full drums a distance 1076.9264 from the
end, and a truck with 5 Gallons in the tank. The rest of the solution
is the same as the unlimited cache solution. The distances obtained for
419 1/11 Gallons or less are the same as the unlimited cache problem
solutions. Once the depot sites are over 1/2 of a tank apart the
limited and unlimited solutions converge. The key to finding
cache-limited solutions is to realize that gas stored in the tank
beyond what is necessary for the return trip is only useful if the
truck continues on past the previously established depot sites.

minimum gas in tank on trip out leaving depot site
Gas Distance Trip 1 Trip 2 Trip 3 Trip 4 Trip 5 Trip 6^
305.00000 1076.9264 Begin unlimited cache solution.
360.00000 1126.9264 10.000000 10.000000 10.000000 10.000000 10.000000 10.00( 1)
419.09091 1172.3810 9.090909 10.000000 10.000000 10.000000 10.000000 10.00( 2)
477.83217 1211.5418 7.832168 10.000000 10.000000 10.000000 10.000000 10.00( 3)
536.95571 1246.3203 6.955711 10.000000 10.000000 10.000000 10.000000 10.00( 4)
596.24050 1277.5229 6.240505 10.000000 10.000000 10.000000 10.000000 10.00( 5)
655.65889 1305.8173 5.658894 10.000000 10.000000 10.000000 10.000000 10.00( 6)
715.17534 1331.6941 5.175343 10.000000 10.000000 10.000000 10.000000 10.00( 7)
774.69915 1355.5036 4.761905 9.937248 10.000000 10.000000 10.000000 10.00( 8)
833.46847 1377.2700 4.353283 9.115188 10.000000 10.000000 10.000000 10.00( 9)
892.49485 1397.6239 4.070785 8.424068 10.000000 10.000000 10.000000 10.00(10)
951.71166 1416.7261 3.820439 7.891224 10.000000 10.000000 10.000000 10.00(11)
1011.0079 1434.6947 3.593709 7.414148 10.000000 10.000000 10.000000 10.00(12)
1070.3790 1451.6578 3.392636 6.986344 10.000000 10.000000 10.000000 10.00(13)
1129.8185 1467.7226 3.212949 6.605584 10.000000 10.000000 10.000000 10.00(14)
1188.9094 1482.8741 3.030303 6.243252 9.635887 10.000000 10.000000 10.00(15)
1247.9074 1497.2638 2.877949 5.908252 9.121201 10.000000 10.000000 10.00(16)
1307.0368 1511.0149 2.750205 5.628155 8.658458 10.000000 10.000000 10.00(17)
1366.2771 1524.1794 2.632900 5.383105 8.261054 10.000000 10.000000 10.00(18)
1425.5876 1536.7986 2.523851 5.156751 7.906956 10.000000 10.000000 10.00(19)
1484.9494 1548.9133 2.422932 4.946783 7.579683 10.000000 10.000000 10.00(20)
1544.2517 1560.5412 2.325581 4.748514 7.272365 9.905264 10.000000 10.00(21)
1603.2522 1571.6734 2.226433 4.552014 6.974946 9.498797 10.000000 10.00(22)
1662.3493 1582.4183 2.148987 4.375420 6.701001 9.123934 10.000000 10.00(23)
1721.5317 1592.8012 2.076574 4.225561 6.451994 8.777576 10.000000 10.00(24)
1780.7890 1602.8448 2.008723 4.085297 6.234284 8.460717 10.000000 10.00(25)
1840.1078 1612.5692 1.944879 3.953601 6.030175 8.179163 10.000000 10.00(26)
1899.4662 1621.9911 1.884394 3.829273 5.837995 7.914569 10.000000 10.00(27)
1958.5571 1631.0820 1.818182 3.702576 5.647455 7.656177 9.732751 10.00(28)
2017.6432 1639.9009 1.763763 3.581945 5.466339 7.411218 9.419940 10.00(29)

Here are some examples of how to use the table to construct solutions:

Given 26 full barrels and one partially full barrel with 7.0368 Gallons
in it (for a total of 1307.0368 Gallons), one sees that the optimal
distance is 1511.0149 Miles. There will be 19 (17+1+1) trips starting
with full gas tanks, and 3 trips with partially full tanks. A total of
22 drums will be moved from the start, using 21 round trips and one
one-way trip.

Trip 1 will take a total of 2.750205 Gallons from drums 23-27, and take
drum 22 13.7511 miles and return.

13.7511=1511.0149-1497.2638, 2.7502=2*13.751/10

Trip 3 will take a total of 8.658458 Gallons from drums 23-27, and take
drum 20 43.2923 miles and return.

43.2923=1511.0149-1467.7226, 8.6584=2*43.292/10

Notice that this trip does not use any gas from drums 21 or 22.

Trip 6 will take a total of 10 Gallons from drums 23-27, 2.750205
Gallons from drum 22, 2.877949 Gallons from drum 21, 3.030303 Gallons
from drum 20, and 0.199293 [=3.212949-(10-6.986344)] from drum 19, no
gas from drum 18 and take drum 17 a total of 94.2888 miles and return.

94.2888=1511.0149-1416.7261, 10+2.7502+2.8779+3.0303+.1993=18.8577=2*94.2888/10

Trip 21 will fill up at every depot site on the way up, leave drum 2 at
1076.9624, and take just enough gas from each site to return to the
next one.

Trip 22 will empty all the drums as it passes and end up at 1076.9264
with 6 full drums and 5 Gallons of gas in the tank.

Check on gas use at a depot site:

The total gas taken from drum 19 is 0.199293+(15+0.5)*3.212949=50
Gallons.

If only 1306.038 Gallons were available, then the optimal distance
decreases by 10*1/(21*2+1), and the starting gas amounts would decrease
by 2/(21*2+1) for the first 21 trips and by 1/(21*1+1) for the last
trip. No other rows need to be changed.

The gas amounts in the Trip 1 column are always the amounts to go to
the next depot site and back.

The optimal distances can be obtained with other fueling schedules than
those presented here. In particular, there is considerable flexibility
in how to allot the gas at the start and at the first depot site.

Since the question is often posed in terms of optimal distance for a
number of drums, the following table is provided.

# of Drums 8 9 10 11 12 13
Distance 1157.6965 1192.9870 1224.5817 1253.1858 1279.3131 1303.1226
# of Drums 14 15 16 17 18 19
Distance 1325.0961 1345.6239 1364.8743 1382.9705 1400.0449 1416.1740
# of Drums 20 21 22 23 24 25
Distance 1431.3589 1445.8353 1459.6635 1472.8973 1485.5791 1497.7505
# of Drums 26 27 28 29 30 31
Distance 1509.3784 1520.5622 1531.3545 1541.7808 1551.8644 1561.6258
# of Drums 40 50 60 70 80 100
Distance 1637.2676 1703.4762 1757.5352 1803.2453 1842.8159 1908.9429

Entries can be calculated from the first table. For example, for 19 drums,

1416.1740 = 1416.7261 - 10*(951.71166 - 950)/(15*2 + 1)


Optimal Limited Cache Solutions for the General Case.

Cache and Ferry. (How far can a truck go in a desert?) A pick-up truck
is in the desert beside N gas drums. Each drum is full and contains K
units of gas. The truck's gas tank is empty and holds 1 unit of gas
and the gets 1 unit of distance per unit of gas. The truck can carry
one drum, whether full or empty, in its bed. How far away from the
starting point can you drive the truck?

Consider the problem beginning at the end of the trip and try to find the
minimum amount of gas that must pass any point. The backwards multiple-truck
statement of the problem is as follows:
You are given a truck with an empty gas tank and an empty drum. At
any time you may acquire another truck and drum. The first truck
produces one unit of gas for every unit of distance traveled.
Additional trucks produce two units of gas per unit of distance. The
gas is created in the truck's gas tank. It may be removed and placed
into any unfilled drum. No gas may be placed into a truck's gas tank
and all gas must be placed somewhere. You cannot get rid of a truck
unless you can place all of the gas in its tank and drum into other
drums. Your objective is to have traveled as far as possible when
the total gas in your caravan is N K.

The optimal strategy is clear:
Never take gas from a tank until it is full, i.e., you have to.
Get a new truck and drum only when all current drums are full.
In other words, always drive as far as you possibly can before getting
another truck and drum.

Here is the outline of an algorithm to find the optimal solution.
At each stage of the backwards trip: compute the distances that the
current caravan must travel to have each of the following occur:
1. D1 distance until the total gas in the caravan is N K.
2. D2 distance until all the available drums are full.
3. D3 distance until a partially full gas tank is filled.
We must keep track of:
1. NV number of vehicles=number of drums
2. NTPF number of partially full tanks
3. PD amount in the partially filled drum
4. PT(1,NTPF) amounts in partially filled tanks
5. GT total gas in the caravan
6. DT distance traveled to current stage
Determine the minimum of D1, D2, and D3; increment DT; and adjust the other
variables as need (e.g., add another drum and truck if D2 was the minimum).
Continue until GT = N K. Where we get new drums are depot sites and the PT
amounts are the amounts of gas as we leave the sites.


Here is a program to find the values in the first table (or
for any other drum and tank sizes and mileages).

; A program to compute the optimal limited cache distances
; and depot sites for any combination of drum capacities (cdrum),
; tank capacities (ctank), mileage (munit), and number of drums (ndrum).
cdrum=0.D & ctank=0.D & munit=0.D & ndrum=0
read,'cdrum,ctank,munit,ndrum ',cdrum,ctank,munit,ndrum
; Initialize variables.
ratio=cdrum/ctank & factor=ctank*munit
gused=0.D & gstart=ndrum*ratio
ntrucks=1 & ntfill=0 & ntpart=1 & ndrums=1
tpart=dblarr(ndrum)
dtot=0.D & dpart=0.D
; If we only need 1 truck, solve immediately.
if gstart lt ratio+1. then begin
print,' Trivial. Distance is ',gstart*factor
stop
endif
ntrucks=2 & ntfill=1 & ntpart=1 & ndrums=2
gused=ratio+1. & dtot=ratio+1.
; Work backwards.
while gstart gt gused do begin
; How far until another tank is full?
dtank=10.^10.D
if ntpart gt 0 then dtank=(1.-tpart(0))/2.
; How far until all the gas is used?
dend=(gstart-gused)/(2*ntrucks-1)
; How far until another drum is full?
dfill=(ratio-dpart)/(2*ntfill-1)
; Do you fill a tank first?
if dtank lt dend and dtank le dfill then begin
gused=gused+dtank*(2*ntrucks-1)
dtot=dtot+dtank
dpart=dpart+dtank*(2*ntfill-1.)
ntfill=ntfill+1
ntpart=ntpart-1
if ntpart gt 0 then for i=0,ntpart-1 do tpart(i)=tpart(i+1)+dtank*2
tpart(ntpart)=0.
; print, '1. full tank',ntfill,' gas used',gused*ctank,' Distance',dtot*factor
endif
; Do you reach the solution first?
if dend le dtank and dend le dfill then begin
gused=gused+dend*(2*ntrucks-1)
dtot=dtot+dend
dpart=dpart+dend*(2*ntfill-1)
if ntpart gt 0 then for i=0,ntpart-1 do tpart(i)=tpart(i)+dend*2
print, '2. Solution gas used',gused*ctank,' Distance',dtot*factor
endif
; Do you fill a drum first?
if dfill lt dend and dfill lt dtank then begin
gused=gused+dfill*(2*ntrucks-1)
dtot=dtot+dfill
if ntpart gt 0 then for i=0,ntpart-1 do tpart(i)=tpart(i)+dfill*2
ntpart=ntpart+1
tpart(ntpart-1)=0.0
dpart=0.
ndrums=ndrums+1
ntrucks=ntrucks+1
print, '3. full drum',ndrums-1,' Gas used',gused*ctank,$
' Distance',dtot*factor
ff='('+str(ntpart)+'f10.6,a24)'
if tpart(0) gt 0.0 then print, reverse(tpart(0:ntpart-2)*ctank),$
ctank,' in the next '+string(ntfill,format='(i4)')+' trucks',format=ff
if tpart(0) eq 0.0 then print, ctank,' in the next '+str(ntfill)+' trucks'
endif
endwhile
end

;SAMPLE RUN
;cdrum,ctank,munit,ndrum 50. 10. 10. 19
;3. full drum 2 Gas used 120.00000 Distance 800.00000
; 10.000000 in the next 2 trucks
;3. full drum 3 Gas used 180.00000 Distance 920.00000
; 10.000000 in the next 3 trucks
;3. full drum 4 Gas used 240.00000 Distance 1005.7143
; 10.000000 in the next 4 trucks
;3. full drum 5 Gas used 300.00000 Distance 1072.3810
; 10.000000 in the next 5 trucks
;3. full drum 6 Gas used 360.00000 Distance 1126.9264
; 10.000000 in the next 6 trucks
;3. full drum 7 Gas used 419.09091 Distance 1172.3810
; 9.090909 10.000000 in the next 6 trucks
;3. full drum 8 Gas used 477.83217 Distance 1211.5418
; 7.832168 10.000000 in the next 7 trucks
;3. full drum 9 Gas used 536.95571 Distance 1246.3203
; 6.955711 10.000000 in the next 8 trucks
;3. full drum 10 Gas used 596.24050 Distance 1277.5229
; 6.240505 10.000000 in the next 9 trucks
;3. full drum 11 Gas used 655.65889 Distance 1305.8173
; 5.658894 10.000000 in the next 10 trucks
;3. full drum 12 Gas used 715.17534 Distance 1331.6941
; 5.175343 10.000000 in the next 11 trucks
;3. full drum 13 Gas used 774.69915 Distance 1355.5036
; 4.761905 9.937248 10.000000 in the next 11 trucks
;3. full drum 14 Gas used 833.46847 Distance 1377.2700
; 4.353283 9.115188 10.000000 in the next 12 trucks
;3. full drum 15 Gas used 892.49485 Distance 1397.6239
; 4.070785 8.424068 10.000000 in the next 13 trucks
;2. Solution gas used 950.00000 Distance 1416.1740

(Lawrence E. Flynn)

References:

C.G. Phipps, The jeep problem : a more general solution, American
Mathematical Monthly, 54, pp 458-62, (1947).
Unlimited cache problem and solution.

G.G. Alway, Crossing the desert, Mathematical Gazette, 41(209),
Note #2707 (1957).
Half way across in one one load problem and solution.

The limited cache problem is the same as the "Desert Fox" problem
described, but not solved, by A. K. Dewdney, July 1987, "Scientific
American."

Dewdney's October 1987 Scientific American article gives for N=2, the
optimal distance of 733.33 miles.

In the November issue, Dewdney lists the optimal distance of 860 miles
for N=3, and gives a better, but not optimal, general distance
formula.

Westbrook, in Vol 74, #467, pp 49-50, March 1990 "Mathematical Gazette",
gives an even better formula, for which he incorrectly claims optimality:

For N = 2,3,4,5,6:
Dist = (600/1 + 600/3 + ... + 600/(2N-3)) + (600-100N)/(2N-1)
For N > 6:
Dist = (600/1 + 600/3 + ... + 600/9) + (500/11 + ... + 500/(2N-3))

The following shows that Westbrook's formula is not optimal for N=8:

Ferry 7 drums forward 33.3333 miles (356.6667 gallons remain)
Ferry 6 drums forward 51.5151 miles (300.0000 gallons remain)
Ferry 5 drums forward 66.6667 miles (240.0000 gallons remain)
Ferry 4 drums forward 85.7143 miles (180.0000 gallons remain)
Ferry 3 drums forward 120.0000 miles (120.0000 gallons remain)
Ferry 2 drums forward 200.0000 miles ( 60.0000 gallons remain)
Ferry 1 drums forward 600.0000 miles
---------------
Total distance = 1157.2294 miles
(Westbrook's formula = 1156.2970 miles)

["Ferrying n drums forward x miles" involves (2*n-1) trips,
each of distance x.]

Well, you did ask! :wink:

Is that the same problem???
I find it hard to see that you are solving the problem I posed.

I was asking for the minumum number of tankfuls to get across a desert, given that the truck can only carry enough to get half-way.

Maybe the problem you're presenting is similar, but I can't see that it's the same.

Sorry if I'm being dense.

Pjnbarb.

Don't mind Tryagain, he sometimes gets carried away with overly long answers to questions nobody asked. It's usually a sign he's been drinking again.

Do you still need the answer?

Answers
Thanks Adrian. I have an answer, but I've never seen anyone else's answer. My answer is nowhere as complex as what was posted by TryAgain. But then I don't know until I see another's solution.

PJ

A passing drover by the name of Mr A. Drian states, "questions nobody asked"

Somebody asked the question, Everybody knew the answer, Anybody could have answered, but in the end Nobody did.

"It's usually a sign he's been drinking again"

Again! That would, wrongly suggest that there was some sort of interruption in proceedings. This might be the first mistake you have made.

How about:

A small pick-up truck is deposited in the desert beside three 50-gallon gas drums, all full. The truck's gas tank holds 10 gallons and is empty. The truck can carry one drum, whether full or empty, in its bed. It gets 10 miles to the gallon.

How far away from the starting point can you drive the truck?

I give up !!
I keep asking my original question, and TryAgain keeps answering and/or posing different questions. Should I give up? or try again?

pjnbarb. Welcome to A2K.

The answer I got involved dividing the journey into sixths and the fuel into thirds. Is that the approach you took?

Sir Tryagain.



I'm intrigued. Who is this Nobody, and did they answer correctly?

Try reading the question again.

This is the Spaceship journey to planet X riddle. Not the Bananas in the desert by camel riddle.

You've been doing too many pure math riddles Try. After a while it starts to affect your basic english comprehension skills.

Verily I suggest a reduction in thou intake of mead good knight.

Odd numbers
The approach I used begins by stating that each point in the journey must be traversed an odd number of times.

Thus, maximize the distance traversed the fewest number of times: once, 3 times, 5 times, 7 times, etc. like so ..............

1. If you can reach the halfway point with a full load, you can get across.

2. In order to maximize the distance traversed 3 times, you must get to the halfway point less 1/6 of the distance (call this point A) with 2 full loads. Then you can go to the middle (using 1/3 load), deposit 1/3 load, and returnto A. Now go to middle again, using 1/3 load, with 2/3 load remaining; pick up the 1/3 waiting for and proceed as in 1 above.

3. In order to maximize the distance traversed 5 times, you must get to point A less 1/10 of the distance (call this point B) with 3 full loads. Then travel from B to A (using 1/5 load), deposit 3/5 load and return to A. Do this a 2nd time, and you will have set up a store of 3/5 * 2 = 6/5 load at point A. For the 3rd trip, use 1/5 load to get to point A, leaving 4/5 load. Now you have 2 full loads (6/5 + 4/5) at point A and you can proceed as in 2. above.

4. etc, etc, etc

Is this what you had in mind???? or is it too simplistic?

There is no such thing as too simplistic.

I hate maths so I try and solve these things in my head rather than on paper. Here's my reasoning.

1. In order to get all the way across you need to deposit 1 whole load of fuel at the halfwway mark. Think of it as 3/3 rather than 1.

2. Divide the journey up into sixths. Then work from there. To deposit 1/3 of a load of fuel 1/6 of the way takes 1 load.

3. Once you have 2/3 of a load 1/6 of the way in you can then get 1/3 of a load 2/6 of the way. That means that for every 3 loads you can get 1/3 of a load deposited 2/6 of the way.

4. Once you have 4/3 of a load 2/6 of the way you can then get 1/3 of a load 3/6 of the way. That means that for every 12 loads you can get 1/3 of a load deposited 3/6 of the way.

5. You need 3/3 deposited 3/6 of the way to complete the trip. This will take 36 loads, so the complete journey will take 37 loads of fuel. 36 to deposit the fuel needed at the halfway mark and 1 load to get you to the halfway mark the final time.

I have no proof that this is the ideal solution but I can't think of any logical way to beat it.

Minimum
Adrian ... your result of 36 loads is certainly not the minimum. If you follow my method out to its conclusion, you will see that it takes under 8 loads to get across. I don't know if that's the minimum, but with a little hand-waving I think I could convince you logically.

I must be missing a huge part of your reasoning. If you feel like explaining I would be interested.

I don't know that it is optimal, but I get 14 loads working backwards.

1 load is needed at the 1/2 point.

2 loads are needed at the 1/3 point. (1 load deposits 1/3 load at the 1/2 point, 1 load gets you to the 1/2 point with 2/3 load, you now have 1 load a the 1/2 point)

5 loads are needed at the 1/6 point. (4 loads deposit 4/3 loads at the 1/3 point, 1 load gets you to the 1/3 point with 2/3 load, you now have 2 loads at the 1/3 point)

14 loads are needed at the 0 point (beginning). (13 loads deposit 13/3 loads at the 1/6 point, 1 load gets you to the 1/6 point with 2/3 load, you now have 5 loads at the 1/6 point).

pjnbarb: Could you map out your 8 load solution in a similar fashion (without the etc.)?