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( 1) 419.09091 1172.3810 9.090909 10.000000 10.000000 10.000000 10.000000 10( 2) 477.83217 1211.5418 7.832168 10.000000 10.000000 10.000000 10.000000 10( 3) 536.95571 1246.3203 6.955711 10.000000 10.000000 10.000000 10.000000 10( 4) 596.24050 1277.5229 6.240505 10.000000 10.000000 10.000000 10.000000 10( 5) 655.65889 1305.8173 5.658894 10.000000 10.000000 10.000000 10.000000 10( 6) 715.17534 1331.6941 5.175343 10.000000 10.000000 10.000000 10.000000 10( 7) 774.69915 1355.5036 4.761905 9.937248 10.000000 10.000000 10.000000 10( 8) 833.46847 1377.2700 4.353283 9.115188 10.000000 10.000000 10.000000 10( 9) 892.49485 1397.6239 4.070785 8.424068 10.000000 10.000000 10.000000 10(10) 951.71166 1416.7261 3.820439 7.891224 10.000000 10.000000 10.000000 10(11)

1011.0079 1434.6947 3.593709 7.414148 10.000000 10.000000 10.000000 10(12) 1070.3790 1451.6578 3.392636 6.986344 10.000000 10.000000 10.000000 10(13) 1129.8185 1467.7226 3.212949 6.605584 10.000000 10.000000 10.000000 10(14) 1188.9094 1482.8741 3.030303 6.243252 9.635887 10.000000 10.000000 10(15) 1247.9074 1497.2638 2.877949 5.908252 9.121201 10.000000 10.000000 10(16) 1307.0368 1511.0149 2.750205 5.628155 8.658458 10.000000 10.000000 10(17) 1366.2771 1524.1794 2.632900 5.383105 8.261054 10.000000 10.000000 10(18) 1425.5876 1536.7986 2.523851 5.156751 7.906956 10.000000 10.000000 10(19) 1484.9494 1548.9133 2.422932 4.946783 7.579683 10.000000 10.000000 10(20) 1544.2517 1560.5412 2.325581 4.748514 7.272365 9.905264 10.000000 10(21) 1603.2522 1571.6734 2.226433 4.552014 6.974946 9.498797 10.000000 10(22) 1662.3493 1582.4183 2.148987 4.375420 6.701001 9.123934 10.000000 10(23) 1721.5317 1592.8012 2.076574 4.225561 6.451994 8.777576 10.000000 10(24) 1780.7890 1602.8448 2.008723 4.085297 6.234284 8.460717 10.000000 10(25) 1840.1078 1612.5692 1.944879 3.953601 6.030175 8.179163 10.000000 10(26) 1899.4662 1621.9911 1.884394 3.829273 5.837995 7.914569 10.000000 10(27) 1958.5571 1631.0820 1.818182 3.702576 5.647455 7.656177 9.732751 10(28) 2017.6432 1639.9009 1.763763 3.581945 5.466339 7.411218 9.419940 10(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= 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

-- flynn@ozone.stx.com (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.]