Sources page biographical material

5.N. JEEP OR EXPLORER'S PROBLEM
See Ball for some general discussion and notation.
Alcuin. 9C. Prob. 52: Propositio de homine patrefamilias. Wants to get 90 measures over a distance of 30 leagues. He is trying to get the most to the other side, so this is different than the 20C versions. Solution is confusing, but Folkerts rectifies a misprint and this makes it less confusing. Alcuin's camels only eat when loaded!! (Or else they perish when their carrying is done??) The camel take a load to a point 20 leagues away and leaves 10 there, then returns. This results in getting 20 to the destination.

The optimum solution is for the camel to make two return trips and a single trip to 10 leucas, so he will have consumed 30 measures and he has 60 measures to carry on. He now makes one return and a single trip of another 15 leucas, so he will have consumed another 30 measures, leaving 30 to carry on the last 5 leucas, so he reaches home with 25 measures.

Pacioli. De Viribus. c1500. Probs. 49 52. Agostini only describes Prob. 49 in some detail.

Ff. 94r - 95v. XLIX. (Capitolo) de doi aportare pome ch' piu navanza (Of two ways to transport as many apples as possible). = Peirani 134 135. One has 90 apples to transport 30 miles from Borgo [San Sepolcro] to Perosia [Perugia], but one eats one apple per mile and one can carry at most 30 apples. He carries 30 apples 20 miles and leaves 10 there and returns, without eating on the return trip! (So this = Alcuin.) Pacioli continues and gives the optimum solution!

F. 95v. L. C(apitolo). de .3. navi per .30. gabelle 90. mesure (Of three ships holding 90 measures, passing 30 customs points). Each ship has to pay one measure at each customs point. Mathematically the same as the previous.

F. 96r. LI. C(apitolo). de portar .100. perle .10. miglia lontano 10. per volta et ogni miglio lascia 1^a (To carry 100 pearls 10 miles, 10 at a time, leaving one every mile). = Peirani 136-137. Takes them 2 miles in ten trips, giving 80 there. Then takes them to the destination in 8 trips, getting 16 to the destination.

Ff. 96v - 97r. LII. C(apitolo). el medesimo con piu avanzo per altro modo (The same with more carried by another method). Continues the previous problem and takes them 5 miles in ten trips, giving 50 there. Then takes them to the destination in 5 trips, getting 25 to the destination.

[This is optimal for a single stop -- if one makes the stop at distance a, then one gets a(10-a) to the destination. One can make more stops, but this is restricted by the fact that pearls cannot be divided. Assuming that the amount of pearls accumulated at each depot is a multiple of ten, one can get 28 to the destination by using depots at 2 and 7 or 5 and 7. One can get 27 to the destination with depots at 4 and 9 or 5 and 9. These are all the ways one can put in two depots with integral multiples of 10 at each depot and none of these can be extended to three such depots. If the material being transported was a continuous material like grain, then I think the optimal method is to first move 1 mile to get 90 there, then move another 10/9 to get 80 there, then another 10/8 to get 70 there, ..., continuing until we get 40 at 8.4563..., and then make four trips to the destination. This gets 33.8254 to the destination. Is this the best method??]

Cardan. Practica Arithmetice. 1539. Chap. 66, section 57, ff. EE.vi.v - EE.vii.v (pp. 152 153). Complicated problem involving carrying food and material up the Tower of Babel! Tower is assumed 36 miles high and seems to require 15625 porters.

Mittenzwey. 1880. Prob. 135, pp. 28-29; 1895?: 153, p. 32; 1917: 153, pp. 29. If eight porters can carry eight full loads from A to B in an hour, how long will it take four porters? The obvious answer is two hours, but he observes that the porters have to return from B to A and it will take three hours. [Probably a little less as they should return in less time than they go.]

Pearson. 1907. Part II, pp. 139 & 216. Two explorers who can carry food for 12 days. (No depots, i.e. form A of Ball, below.)

Loyd. A dash for the South Pole. Ladies' Home Journal (15 Dec 1910). ??NYS -- source?? -- WS??

Ball. MRE, 5th ed., 1911. Exploration problems, pp. 23 24. He distinguishes two forms of the problem, with n explorers who can carry food for d days.

A. Without depots, they can get one man nd/(n+1) days into the desert and back.

B. With depots permitted, they can get a man d/2 (1/1 + 1/2 + ... + 1/n) into the desert and back. This is the more common form.

Dudeney. Problem 744: Exploring the desert. Strand Mag. (1925). ??NX. (??= MP 49)

Dudeney. MP. 1926. Prob. 49: Exploring the desert, pp. 21 & 111 (= 536, prob. 76, pp. 22 & 240). A version of Ball's form A, with n = 9, d = 10, but replacing days by stages of length 40 miles.

Abraham. 1933. Prob. 34 -- The explorers, pp. 13 & 25 (9 10 & 112). 4 explorers, each carrying food for 5 days. Mentions general case. This is Ball's form A.

Haldeman-Julius. 1937. No. 10: The four explorers, pp. 4 & 21. Ball's form A, with n = 4, d = 5.

Olaf Helmer. Problem in logistics: The Jeep problem. Project Rand Report RA 15015 (1 Dec 1946) 7pp.

N. J. Fine. The jeep problem. AMM 54 (1947) 24 31.

C. G. Phipps. The jeep problem: a more general solution. AMM 54 (1947) 458 462.

G. G. Alway. Note 2707: Crossing the desert. MG 41 (No. 337) (1957) 209. If a jeep can carry enough fuel to get halfway across, how much fuel is needed to get across? For a desert of width 2, this leads to the series 1 + 1/3 + 1/5 + 1/7 + .... See Lehmann and Pyle below.

G. C. S[hephard, ed.] The problems drive. Eureka 11 (Jan 1949) 10-11 & 30. No. 2. Four explorers, starting from a supply base. Each can carry food for 100 miles and goes 25 miles per day. Two men do the returning to base and bringing out more supplies. the third man does ferrying to the fourth man. How far can the fourth man get into the desert and return? Answer is 100 miles. Ball's form B would give 104 1/6.

Gamow & Stern. 1958. Refueling. Pp. 114 115.

Pyle, I. C. The explorer's problem. Eureka 21 (Oct 1958) 5-7. Considers a lorry whose load of fuel takes it a distance which we assume as the unit. What is the widest desert one can cross? And how do you do it? This is similar to Alway, above. He starts at the far side and sees you have to have a load at distance 1 from the far side, then two loads at distance 1 + 1/3 from the far side, then three loads at 1 + 1/3 + 1/5, .... This diverges, so any width can be crossed. Does examples with given widths of 2, 3 and 4 units. Editor notes that he is not convinced the method is optimal.

Martin Gardner, SA (May & June 1959) c= 2nd Book, chap. 14, prob. 1. (The book gives extensive references which were not in SA.)

R. L. Goodstein. Letter: Explorer's problem. Eureka 22 (Oct 1959) 23. Says Alway shows that Pyle's method is optimal. Editor notes Gardner's article and that Eureka was cited in the solutions in Jun.

David Gale. The jeep once more or jeeper by the dozen & Correction to "The Jeep once more or jeeper by the dozen". AMM 77:5 (May 1970) 493-501 & 78:6 (Jun-Jul 1971) 644-645. Gives an elaborate approach via a formula of Banach for path lengths in one dimension. This formally proves that the various methods used are actually optimal and that a continuous string of depots cannot help, etc. Notes that the cost for a round trip is only slightly more than for a one-way trip -- but the Correction points out that this is wrong and indeed the round trip is nearly four times as expensive as a one-way trip. Considers sending several jeeps. Says he hasn't been able to do the round trip problem when there is fuel on both sides of the desert. Comments on use of dynamic programming, noting that R. E. Bellman [Dynamic Programming; Princeton Univ. Press, 1955, p. 103, ex. 54-55] gives the problem as exercises without solution and that he cannot see how to do it!

Birtwistle. Math. Puzzles & Perplexities. 1971.

The expedition, pp. 124-125, 183 & 194. Ball's form A, first with n = 5, d = 6, then in general.

Second expedition, pp. 125-126. Ball's form B, done in general.

Third expedition, pp. 126, 183-184 & 194. Three men want to cross a 180 mile wide desert. They can travel 20 miles per day and can carry food for six days, which can be stored at depots. Minimize the total distance travelled. Solution seems erroneous to me.

A. K. Austin. Jeep trips and card stacks. MTg 58 (1972) 24 25. There are n flags located at distances a₁, a₁ + a₂, a₁ + a₂ + a₃, .... Jeep has to begin at the origin, go to the first flag, return to the origin, go to the second flag, return, .... He can unload and load fuel at the flags. Can he do this with F fuel? Author shows this is equivalent to successfully stacking cards over a cliff with successive overhangs being a₁, a₂, a₃, ....

Doubleday - 3. 1972. Traveller's Tale, pp. 63-64. d = 8 and we want one man to get across the desert of width 12. How many porters, who return to base, are needed? The solution implies that no depots are used. Reasoning as in Ball's case A, we see that n men can support one man crossing a desert of width 2nd/(n+1). If depots are permitted, this is essentially the jeep problem and n men can support a man getting across a desert of width d [1 + 1/3 + 1/5 + ... + 1/(2n-1)]

Johannes Lehmann. Kurzweil durch Mathe. Urania Verlag, Leipzig, 1980. No. 13, pp. 27 & 129. d = 4 and we want to get a man across a desert of width 6. Similar to Doubleday - 3.

Pierre Berloquin. [Le Jardin du Sphinx. Dunod, Paris, 1981.] Translated by Charles Scribner Jr as: The Garden of the Sphinx. Scribner's, NY, 1985.

Prob. 1: Water in the desert, pp. 3 & 85.

Prob. 40: Less water in the desert, pp. 26 & 111.

Prob. 80: Beyond thirst, pp. 48 & 140.

Prob. 141: The barrier of thirst, pp. 79 & 181.

Prob. 150: No holds barred, pp. 82 & 150.

In all of these, d = 5 and we want to get a man across a desert of width 4, and sometimes back, which is slightly different than the problem of getting to the maximum distance and back.

Prob. 1 is Ball's form A, with n = 4 men, using 20 days' water.

Prob. 40 is Ball's form B, but using only whole day trips, using 14 days' water.

Prob. 80 is Ball's form B, optimized for width 4, using 11½ days' water.

Prob. 141 uses depots and bearers who don't return, as in Alcuin?? You can get one man, who is the only one to return, a distance d (1/2 + 1/3 + ... + 1/(n+1)) into the desert this way. He gives the optimum form for width 4, using 9½ days' water.

Prob. 150 is like prob. 141, except that no one returns! You can get him d (1 + 1/2 + ... + 1/n) into the desert this way. The optimum here uses 4 days' water.

D. R. Westbrook. Note 74.7: The desert fox, a variation of the jeep problem. MG 74 (No. 467) (1990) 49 50. A more complex version, posed by A. K. Dewdney in SA (Jan 1987), is solved here.

Liz Allen. Brain Sharpeners. Op. cit. in 5.B. 1991. Round-trip, pp. 96-97 & 140. Plane wants to circle the earth, but can only carry fuel to go half-way. Other planes can accompany and transfer fuel, but must return to base.

Dylan Gow. Flyaway. MS 25:3 (1992/3) 84-86. Considers the standard problem without return as in Alway, Pyle and Lehmann -- but finds a non-optimal solution.

Wolfram Hinderer. Optimal crossing of a desert. MS 26:4 (1993/4) 100-102. Finds optimal solutions for Gow's problem and for the case with return -- i.e. Ball's B. Also considers use of extra jeeps that do not return, i.e. Berloquin's 141 & 150. Notes that extra jeeps that must return to base do not change the distance that one jeep can reach. [But it changes the time required.]

Harold Boas. Letter: Crossing deserts. MS 26:4 (1993/4) 122. Notes the problem has a long history and cites Fine, Phipps, Gale (and correction), Alway.

David Singmaster. Letter: Crossing deserts. MS 27:3 (1994/5) 63. Points out that the history is far older and sketches the history given above.

Günter Rote & Guochuan Zhang. Optimal Logistics for Expeditions: The Jeep Problem with Complete Refilling. Karl-Franzens-Universität Graz & Technische Universität Graz. Bericht 71 (24 Jun 1996). This deals with a variant. "We have n cans of fuel on the edge of a desert and a jeep with an empty tank whose capacity is just one can. The jeep can carry one can in addition to the fuel in its tank. Moreover, when a can is opened, the fuel must immediately be filled into the jeep's tank. The goal is to find the farthest point in the desert which the jeep can reach by consuming the n cans of fuel. Derick Wood [1984] treated this problem similarly to the classical problem and gave the first solution. Ute and Wilfried Brauer [1989] presented a new strategy and got a better solution than Wood's. They also conjectured that their solution was optimal for infinitely many values of n. We give an algorithm which produces a better solution than Brauers' for all n > 6, and we use a linear programming formulation to derive an upper bound which shows that our solution is optimal." 14 references, several not given above.