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

<pre>
	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)
</pre>

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

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

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.

<pre>
                          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)
</pre>

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.

<pre>
        13.7511<code>1511.0149-1497.2638,   2.7502</code>2*13.751/10
</pre>

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

<pre>
        43.2923<code>1511.0149-1467.7226,   8.6584</code>2*43.292/10
</pre>

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<code>1511.0149-1416.7261, 10+2.7502+2.8779+3.0303+.1993</code>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.

<pre>
 # 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
</pre>

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

<pre>
   1416.1740 = 1416.7261 - 10'''(951.71166 - 950)/(15'''2 + 1)
</pre>


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:

<pre>
 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.
</pre>

We must keep track of:

<pre>
 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
</pre>

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).

<pre>
 ; 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<code>0.D & ctank</code>0.D & munit<code>0.D & ndrum</code>
 read,'cdrum,ctank,munit,ndrum ',cdrum,ctank,munit,ndrum
 ; Initialize variables.
 ratio<code>cdrum/ctank  &  factor</code>ctank*munit
 gused<code>0.D  &  gstart</code>ndrum*ratio
 ntrucks<code>1  &  ntfill</code>0  &  ntpart<code>1  &  ndrums</code>1
 tpart=dblarr(ndrum)
 dtot<code>0.D  &  dpart</code>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<code>2  &  ntfill</code>1  &  ntpart<code>1  &  ndrums</code>2
 gused<code>ratio+1.  & dtot</code>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<code>0,ntpart-1 do tpart(i)</code>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<code>0,ntpart-1 do tpart(i)</code>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<code>0,ntpart-1 do tpart(i)</code>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<code>'(i4)')+' trucks',format</code>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
</pre>

-- 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:

<pre>
  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))
</pre>

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

<pre>
   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.]
</pre>
</pre>
