# 29 analysis/cache.p

Cache and Ferry (How far can a truck go in a desert?)
A pick-up truck is in the desert beside N 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?

analysis/cache.s

If the truck can siphon gas out of its tank and leave it in the cache,
{ 1/1 + 1/3 + ... + 1/(2 * N - 1) } x 500 miles.

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.

Now, remarkably, for initial gas values of 50, 100, 150, 200, 250, 300,
and 350 gallons, the two problems give identical optimal distances, viz.

```   gal   dist
---   ----
50   500
100   733.3333
150   860
200   948.5714
250  1016.8254
300  1072.3810
350  1117.8355
```

However, for the 8 barrel case (400 gallons), the unlimited cache optimal
distance is 1157.6957, but limited cache is only 1157.2294.

What happened is that the unlimited cache optimal solution has started to
siphon out more than 50 gallons (60-80/13 to be exact) of gas on trips
to the first depot. With a limited cache, the truck can only leave a
maximum of 50 gallons (one barrel worth), and does not have a big
enough gas tank (only ten gallons) to carry around the excess.

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

Dewdney's Oct. '87 Sci. Am. article gives for N=2, the optimal distance
of 733.33 miles.

In the Nov. 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 '90 "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.]

Other attainable values I've found:

```   N      Distance
---    ---------  (Ferry distances for each N are omitted for brevity.)
5    1016.8254
7    1117.8355
11    1249.2749
13    1296.8939
17    1372.8577
19    1404.1136  (The N <= 19 distances could be optimal.)
31    1541.1550  (I doubt that this N = 31 distance is optimal.)
139    1955.5702  (Attainable and probably optimal.)
```

So...where's MY formula?
I haven't found one, and believe me, I've looked.

I would be most grateful if someone would end my misery by mailing me
a formula, a literature reference, or even an efficient algorithm that
computes the optimal distance.

If you do come up with the solution, you might want to first check it
against the attainable distances listed above, before sending it out.
(Not because you might be wrong, but just as a mere formality to check

[Warning: the Mathematician General has determined that
this problem is as addicting as Twinkies.]

Myron P. Souris
EDS/Unigraphics
souris@ug.eds.com

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

The following output comes from some hack programs that I've used to
empirically verify some proofs I've been working on.

Initial barrels: 12 (600 gallons)
Attainable distance= 1274.175211

```                  Barrels  Distance      Gas
Moved    covered     left
>From depot   1:      10     63.1579   480.0000
>From depot   2:       8     50.0000   405.0000
>From depot   3:       7     37.5000   356.2500
>From depot   4:       6     51.1364   300.0000
>From depot   5:       5     66.6667   240.0000
>From depot   6:       4     85.7143   180.0000
>From depot   7:       3    120.0000   120.0000
>From depot   8:       2    200.0000    60.0000
>From depot   9:       1    600.0000     0.0000
```

Initial barrels: 40 (2000 gallons)
Attainable distance= 1611.591484

```                  Barrels  Distance      Gas
Moved    covered     left
>From depot   1:      40      2.5316  1980.0000
>From depot   2:      33     50.0000  1655.0000
>From depot   3:      28     50.0000  1380.0000
>From depot   4:      23     53.3333  1140.0000
>From depot   5:      19     50.0000   955.0000
>From depot   6:      16     56.4516   780.0000
>From depot   7:      13     50.0000   655.0000
>From depot   8:      11     54.7619   540.0000
>From depot   9:       9     50.0000   455.0000
>From depot  10:       8     32.1429   406.7857
>From depot  11:       7     38.9881   356.1012
>From depot  12:       6     51.0011   300.0000
>From depot  13:       5     66.6667   240.0000
>From depot  14:       4     85.7143   180.0000
>From depot  15:       3    120.0000   120.0000
>From depot  16:       2    200.0000    60.0000
>From depot  17:       1    600.0000     0.0000
```

Continue to: