==> analysis/cache.s <==
If the truck can siphon gas out of its tank and leave it in the cache,
the answer is:
{ 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
your work.)
[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