This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

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,

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

Continue to: