Jeep problem

Last updated
Plot of amount of fuel f vs distance from origin d for exploring (1-3) and crossing (I-III) versions of the jeep problem for three units of fuel - coloured arrows denote depots, diagonal segments denote travel and vertical segments denote fuel transfer Jeep problem graphs.svg
Plot of amount of fuel f vs distance from origin d for exploring (1–3) and crossing (I–III) versions of the jeep problem for three units of fuel coloured arrows denote depots, diagonal segments denote travel and vertical segments denote fuel transfer

The jeep problem, [1] desert crossing problem [2] or exploration problem [3] is a mathematics problem in which a jeep must maximize the distance it can travel into a desert with a given quantity of fuel. The jeep can only carry a fixed and limited amount of fuel, but it can leave fuel and collect fuel at fuel dumps anywhere in the desert.

Contents

The problem first appeared in the 9th-century collection Propositiones ad Acuendos Juvenes (Problems to Sharpen the Young), attributed to Alcuin, with the puzzle being about a travelling camel eating grain. [4] The De viribus quantitatis (c. 1500) of Luca Pacioli also discusses the problem. A modern treatment was given by N. J. Fine in 1947. [1]

Variations of the problem are the camel and bananas problem [5] where a merchant must maximize the number of bananas transported to a market using a camel that feeds on the bananas, the travelers across the desert problem [6] where a number of travellers must all reach a destination and can only exchange supplies rather than leaving them, and the cars across the desert problem [7] which again can only exchange their fuel, but where empty cars can be abandoned. This final problem has similarities to the operation of multistage rocket.

Problem

Plot to scale of the Exploring (top) and Crossing (bottom) versions of the jeep problem for three units of fuel. The horizontal axis denotes distance and vertical axis denotes time. Vertical coloured line segments denote stashing fuel and horizontal ones denote travel using withdrawn fuel. Coloured numbers denote units of fuel stashed at that moment. Jeep problem.svg
Plot to scale of the Exploring (top) and Crossing (bottom) versions of the jeep problem for three units of fuel. The horizontal axis denotes distance and vertical axis denotes time. Vertical coloured line segments denote stashing fuel and horizontal ones denote travel using withdrawn fuel. Coloured numbers denote units of fuel stashed at that moment.

There are n units of fuel stored at a fixed base. The jeep can carry at most 1 unit of fuel at any time, and can travel 1 unit of distance on 1 unit of fuel (the jeep's fuel consumption is assumed to be constant). At any point in a trip the jeep may leave any amount of fuel that it is carrying at a fuel dump, or may collect any amount of fuel that was left at a fuel dump on a previous trip, as long as its fuel load never exceeds 1 unit. There are two variants of the problem:

In either case the objective is to maximize the distance traveled by the jeep on its final trip. Alternatively, the objective may be to find the least amount of fuel required to produce a final trip of a given distance.

Variations

In the classic problem the fuel in the jeep and at fuel dumps is treated as a continuous quantity. More complex variations on the problem have been proposed in which the fuel can only be left or collected in discrete amounts. [8]

In the camel and bananas problem, the merchant has n units of bananas. The camel can carry at most 1 unit of bananas at any time, and can travel 1 unit of distance on 1 unit of bananas. The market is at m units of distance away. At any point in a trip the camel may leave any amount of bananas that it is carrying at a camp post, or may collect any amount of bananas that was left at a camp post on a previous trip, as long as its banana load never exceeds 1 unit. The problem asks for the maximum units of bananas that can be transported to the market.

In the travelers across the desert problem, the starting base has unlimited units of supplies. Each traveler can carry at most 1 unit of supplies at any time, and can travel 1 unit of distance on 1 unit of supplies. The other base is at m units of distance away. Contrary to the previous two problems, the travelers can't leave supplies in the desert; However, at any point in a trip, accompanying travelers can transfer supplies among themselves, as long as each traveler never carries more than 1 unit of supplies. Each returning traveler must have enough supplies on the way back. The problem asks for the minimum number of accompanying travelers needed to reach the other base. A variant of this problem gives the total number of travelers available, and asks for the maximum distance that can be reached.

In the cars across the desert problem, the starting base has unlimited units of fuel. Each car can carry at most 1 unit of supplies at any time, and can travel 1 unit of distance on 1 unit of fuel. The other base is at m units of distance away. The cars can't leave fuel in the desert; However, at any point in a trip, accompanying cars can transfer fuel among themselves, as long as each car never carries more than 1 unit of fuel. Empty cars with no fuel are abandoned in the desert. The problem asks for the minimum number of accompanying cars needed to reach the other base. A variant of this problem gives the total number of cars available, and asks for the maximum distance that can be reached.

Solution

Solution to "exploring the desert" variant for n = 3, showing fuel contents of jeep and fuel dumps at start of each trip and at turnround point on each trip. Jeep problem 1.png
Solution to "exploring the desert" variant for n = 3, showing fuel contents of jeep and fuel dumps at start of each trip and at turnround point on each trip.

A strategy that maximizes the distance traveled on the final trip for the "exploring the desert" variant is as follows:

When the jeep starts its final trip, there are n  1 fuel dumps. The farthest contains 1/2 of a unit of fuel, the next farthest contain 1/3 of a unit of fuel, and so on, and the nearest fuel dump has just 1/n units of fuel left. Together with 1 unit of fuel with which it starts from base, this means that the jeep can travel a total round trip distance of

units on its final trip (the maximum distance traveled into the desert is half of this). [3] It collects half of the remaining fuel at each dump on the way out, which fills its tank. After leaving the farthest fuel dump it travels 1/2 a unit further into the desert and then returns to the farthest fuel dump. It collects the remaining fuel from each fuel dump on the way back, which is just enough to reach the next fuel dump or, in the final step, to return to base.

Solution to "crossing the desert" variant for n = 3, showing fuel contents of jeep and fuel dumps at start of each trip, at turnaround point on first two trips, and at end of final trip. Jeep problem 2.png
Solution to "crossing the desert" variant for n = 3, showing fuel contents of jeep and fuel dumps at start of each trip, at turnaround point on first two trips, and at end of final trip.

The distance travelled on the last trip is the nth harmonic number, Hn. As the harmonic numbers are unbounded, it is possible to exceed any given distance on the final trip, as along as sufficient fuel is available at the base. However, the amount of fuel required and the number of fuel dumps both increase exponentially with the distance to be traveled.

The "crossing the desert" variant can be solved with a similar strategy, except that there is now no requirement to collect fuel on the way back on the final trip. So on trip k the jeep establishes a new kth fuel dump at a distance of 1/(2n  2k + 1) units from the previous fuel dump and leaves (2n  2k  1)/(2n  2k + 1) units of fuel there. On each of the next n  k  1 trips it collects 1/(2n  2k + 1) units of fuel from the kth dump on its way out and another 1/(2n  2k + 1) units of fuel on its way back.

Now when the jeep starts its final trip, there are n  1 fuel dumps. The farthest contains 1/3 of a unit of fuel, the next farthest contain 1/5 of a unit of fuel, and so on, and the nearest fuel dump has just 1/(2n  1) units of fuel left. Together with 1 unit of fuel with which it starts from base, this means that the jeep can travel a total distance of

units on its final trip. [1] [3] It collects all of the remaining fuel at each dump on the way out, which fills its tank. After leaving the farthest fuel dump it travels a further distance of 1 unit.

Note that

so it is possible in theory to cross a desert of any size given enough fuel at the base. As before, the amount of fuel required and the number of fuel dumps both increase exponentially with the distance to be traveled.

In summary, the maximum distance reachable by the jeep (with a fuel capacity for 1 unit of distance at any time) in n trips (with n-1 midway fuel dumps and consuming a total of n units of fuel) is

Here is the nth harmonic number.

Continuous amount of fuel

The number of fuel units available at the base need not be an integer. In the general case, the maximum distance achievable for the "explore the desert" problem with n units of fuel is

with the first fuel dump located at units of distance away from the starting base, the second one at units of distance away from the first fuel dump, the third one at units of distance away from the second fuel dump, and so on. Here is the fractional part of n.

The maximum distance achievable for the "cross the desert" problem with n units of fuel is

with the first fuel dump located at units of distance away from the starting base, the second one at units of distance away from the first fuel dump, the third one at units of distance away from the second fuel dump, and so on. Here is the fractional part of n.

Other variants of the problem

In the camel and bananas problem, assuming the merchant has a total of n=7/3 units of bananas at the starting base and the market is at m units of distance away:

If the camel is required to eventually return to the starting base, then the function applies (still assuming n=7/3):

In the travelers across the desert problem, assume that n travelers set out from the starting base with n units of supplies. After 1/(n+1) units of distance, they would have already consumed n/(n+1) units of supplies; At this point, one of the travelers should return with 1/(n+1) units of supplies, leaving the group exactly (n-1) units of supplies so that each remaining traveler carries exactly one unit of supplies. The group then travels another 1/(n+1) units of distance, consuming (n-1)/(n+1) units of supplies; At this point, one of the remaining travelers should return with 2/(n+1) units of supplies to safely get back to the starting base, leaving the group exactly (n-2) units of supplies. The group keeps moving 1/(n+1) units of distance and reducing one traveler, until there is only one traveler left carrying exactly one unit of supplies. Finally, this traveler can travel one unit of distance to reach the farthest point. In total, the longest distance n travelers can reach is

Equating this to m, one may solve for the minimum number of travelers needed to travel m units of distance. Note that solutions only exist for m<2.

If the last and final traveler also needs to return to the starting base, then he would only travel 1/(n+1) unit alone so that he has n/(n+1) units of supply to return, so the longest distance n travelers can reach is

Equating this to m, one may solve for the minimum number of travelers needed to travel m units of distance. Note that solutions only exist for m<1.

In the cars across the desert problem, assume that n cars set out from the starting base with n units of fuel. After 1/n units of distance, the group would have already consumed exactly one unit of fuel; At this point, they should transfer fuel between them, leave an empty car behind, and carry (n-1) units of fuel among (n-1) cars. After another 1/(n-1) units of distance, the group would have consumed another one unit of fuel; Again, they should transfer fuel, leave an empty car behind, and carry (n-2) units of fuel among (n-2) cars. The group keeps moving and reducing one car, until there is only one car left carrying exactly one unit of fuel. Finally, this car can travel one unit of distance to reach the farthest point. In total, the longest distance n cars can reach is the nth harmonic number:

Equating this to m, one may solve for the minimum number of cars needed to travel m units of distance.

Order independence

Note that the order of the jeep trips is not fixed. For example in the "exploring the desert" version of the problem, the jeep could make n − 1 round-trips between the base and the first fuel dump, leaving (n − 1) / n units of fuel at the fuel dump each time and then make an n-th trip one-way to the first fuel dump, thus arriving there with a total of (n − 1) + 1/(2n) units of fuel available. The 1/(2n) units are saved for the return trip to base at the very end and the other n − 1 units of fuel are used to move fuel between the first and second fuel dump, using n − 2 round-trips and then an (n−1)-th trip one-way to the second fuel dump. And so on.

Practical applications

In Operation Black Buck One, the attacking Vulcan was refuelled seven times on the outward journey and once on the return journey. Grey lines indicate reserve aircraft to replace casualties. Refuelling.plan.black.buck.svg
In Operation Black Buck One, the attacking Vulcan was refuelled seven times on the outward journey and once on the return journey. Grey lines indicate reserve aircraft to replace casualties.

The problem can have a practical application in wartime situations, especially with respect to fuel efficiency. In the context of the bombing of Japan in World War II by B-29s, Robert McNamara says in the film The Fog of War that understanding the fuel efficiency issue caused by having to transport the fuel to forward bases was the main reason why the strategy of launching bombing raids from mainland China was abandoned in favor of the island hopping strategy:

"We had to fly those planes from the bases in Kansas to India. Then we had to fly fuel over the hump into China. [...] We were supposed to take these B-29s—there were no tanker aircraft there. We were to fill them with fuel, fly from India to Chengtu; offload the fuel; fly back to India; make enough missions to build up fuel in Chengtu; fly to Yawata, Japan; bomb the steel mills; and go back to India. We had so little training on this problem of maximizing [fuel] efficiency, we actually found to get some of the B-29s back instead of offloading fuel, they had to take it on. To make a long story short, it wasn't worth a damn. And it was LeMay who really came to that conclusion, and led the Chiefs to move the whole thing to the Marianas, which devastated Japan." [9]

(The atomic bombing missions at the end of World War II were flown using B-29 Superfortresses from the Pacific island of Tinian in the Northern Marianas Islands.)

See also Operation Black Buck for an application of these ideas. In these missions, conducted during the Falklands War, the Royal Air Force used air to air refueling by staging tankers to enable the Vulcan bombers based on Ascension Island to bomb targets in the Falkland Islands.

See also

Related Research Articles

In physics, the cross section is a measure of the probability that a specific process will take place when some kind of radiant excitation intersects a localized phenomenon. For example, the Rutherford cross-section is a measure of probability that an alpha particle will be deflected by a given angle during an interaction with an atomic nucleus. Cross section is typically denoted σ (sigma) and is expressed in units of area, more specifically in barns. In a way, it can be thought of as the size of the object that the excitation must hit in order for the process to occur, but more exactly, it is a parameter of a stochastic process.

<span class="mw-page-title-main">Histogram</span> Graphical representation of the distribution of numerical data

A histogram is an approximate representation of the distribution of numerical data. The term was first introduced by Karl Pearson. To construct a histogram, the first step is to "bin" the range of values—that is, divide the entire range of values into a series of intervals—and then count how many values fall into each interval. The bins are usually specified as consecutive, non-overlapping intervals of a variable. The bins (intervals) must be adjacent and are often of equal size.

<span class="mw-page-title-main">Trigonometric functions</span> Functions of an angle

In mathematics, the trigonometric functions are real functions which relate an angle of a right-angled triangle to ratios of two side lengths. They are widely used in all sciences that are related to geometry, such as navigation, solid mechanics, celestial mechanics, geodesy, and many others. They are among the simplest periodic functions, and as such are also widely used for studying periodic phenomena through Fourier analysis.

<span class="mw-page-title-main">Torque</span> Turning force around an axis

In physics and mechanics, torque is the rotational analogue of linear force. It is also referred to as the moment of force. It describes the rate of change of angular momentum that would be imparted to an isolated body.

Radius of gyration or gyradius of a body about the axis of rotation is defined as the radial distance to a point which would have a moment of inertia the same as the body's actual distribution of mass, if the total mass of the body were concentrated there.

<span class="mw-page-title-main">Floor and ceiling functions</span> Nearest integers from a number

In mathematics and computer science, the floor function is the function that takes as input a real number x, and gives as output the greatest integer less than or equal to x, denoted x or floor(x). Similarly, the ceiling function maps x to the least integer greater than or equal to x, denoted x or ceil(x).

<span class="mw-page-title-main">Birthday problem</span> Mathematical problem

In probability theory, the birthday problem asks for the probability that, in a set of n randomly chosen people, at least two will share a birthday. The birthday paradox refers to the counterintuitive fact that only 23 people are needed for that probability to exceed 50%.

In mathematics, the harmonic series is the infinite series formed by summing all positive unit fractions:

In mathematics, the Jacobi elliptic functions are a set of basic elliptic functions. They are found in the description of the motion of a pendulum, as well as in the design of electronic elliptic filters. While trigonometric functions are defined with reference to a circle, the Jacobi elliptic functions are a generalization which refer to other conic sections, the ellipse in particular. The relation to trigonometric functions is contained in the notation, for example, by the matching notation for . The Jacobi elliptic functions are used more often in practical problems than the Weierstrass elliptic functions as they do not require notions of complex analysis to be defined and/or understood. They were introduced by Carl Gustav Jakob Jacobi (1829). Carl Friedrich Gauss had already studied special Jacobi elliptic functions in 1797, the lemniscate elliptic functions in particular, but his work was published much later.

<span class="mw-page-title-main">Lambert series</span> Mathematical term

In mathematics, a Lambert series, named for Johann Heinrich Lambert, is a series taking the form

In mathematics, Birkhoff interpolation is an extension of polynomial interpolation. It refers to the problem of finding a polynomial of degree such that only certain derivatives have specified values at specified points:

Bijective numeration is any numeral system in which every non-negative integer can be represented in exactly one way using a finite string of digits. The name refers to the bijection that exists in this case between the set of non-negative integers and the set of finite strings using a finite set of symbols.

<span class="mw-page-title-main">Comparison sort</span> Type of sorting algorithm that works by comparing pairs of elements

A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation that determines which of two elements should occur first in the final sorted list. The only requirement is that the operator forms a total preorder over the data, with:

  1. if ab and bc then ac (transitivity)
  2. for all a and b, ab or ba (connexity).
<span class="mw-page-title-main">Lemniscate elliptic functions</span> Mathematical functions

In mathematics, the lemniscate elliptic functions are elliptic functions related to the arc length of the lemniscate of Bernoulli. They were first studied by Giulio Fagnano in 1718 and later by Leonhard Euler and Carl Friedrich Gauss, among others.

Discrepancy of hypergraphs is an area of discrepancy theory.

<span class="mw-page-title-main">Wright omega function</span> Mathematical function

In mathematics, the Wright omega function or Wright function, denoted ω, is defined in terms of the Lambert W function as:

In the mathematics of coding theory, the Griesmer bound, named after James Hugo Griesmer, is a bound on the length of linear binary codes of dimension k and minimum distance d. There is also a very similar version for non-binary codes.

In mathematics, a unit sphere is simply a sphere of radius one around a given center. More generally, it is the set of points of distance 1 from a fixed central point, where different norms can be used as general notions of "distance". A unit ball is the closed set of points of distance less than or equal to 1 from a fixed central point. Usually the center is at the origin of the space, so one speaks of "the unit ball" or "the unit sphere". Special cases are the unit circle and the unit disk.

In statistics, the generalized Marcum Q-function of order is defined as

<span class="mw-page-title-main">Parallel external memory</span>

In computer science, a parallel external memory (PEM) model is a cache-aware, external-memory abstract machine. It is the parallel-computing analogy to the single-processor external memory (EM) model. In a similar way, it is the cache-aware analogy to the parallel random-access machine (PRAM). The PEM model consists of a number of processors, together with their respective private caches and a shared main memory.

References

  1. 1 2 3 Weisstein, Eric W. "Jeep Problem". MathWorld .
  2. Gardner, Martin (1994). My Best Mathematical and Logic Puzzles . Dover. pp.  53. ISBN   0-486-28152-3.
  3. 1 2 3 "Exploration problems. Another common question is concerned with the maximum distance into a desert which could be reached from a frontier settlement by an explorer capable of carrying provisions that would last him for a days." W. W. Rouse Ball and H.S.M. Coxeter (1987). Mathematical Recreations and Essays, Thirteenth Edition, Dover, p32. ISBN   0-486-25357-0.
  4. Problems to Sharpen the Young, John Hadley and David Singmaster, The Mathematical Gazette, 76, #475 (March 1992), pp. 102126.
  5. "Puzzle 15 | (Camel and Banana Puzzle)". GeeksforGeeks. 2015-03-11. Retrieved 2020-02-04.
  6. "Travelers across the desert". mathforum.org. Retrieved 2020-02-04.
  7. "Cars Across the Desert Puzzle - Solution". www.mathsisfun.com. Retrieved 2020-02-04.
  8. Optimal Logistics for Expeditions: the Jeep Problem with Complete Refilling, Gunter Rote and Guochuan Zhang, June 1996
  9. Fog of War transcript, www.errolmorris.com