Jeep problem

Last updated October 21, 2024

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.

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]

Problem

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:

Exploring the desert – the jeep must return to the base at the end of every trip.
Crossing the desert – the jeep must return to the base at the end of every trip except for the final trip, when the jeep travels as far as it can before running out of fuel.

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.^[5]

Solution

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

The jeep makes n trips. On each trip it starts from base with 1 unit of fuel.
On the first trip the jeep travels a distance of 1/(2n) units and leaves (n − 1)/n units of fuel at a fuel dump. The jeep still has 1/(2n) units of fuel – just enough to return to base.
On each of the subsequent n − 1 trips the jeep collects 1/(2n) units of fuel from this first fuel dump on the way out, so that it leaves the fuel dump carrying 1 unit of fuel. It also collects 1/(2n) units of fuel from this first fuel dump on the way back, which is just enough fuel to return to base.
On the second trip the jeep travels to the first fuel dump and refuels. It then travels a distance of 1/(2n − 2) units and leaves (n − 2)/(n − 1) units of fuel at a second fuel dump. The jeep still has 1/(2n − 2) units of fuel, which is just enough to return to the first fuel dump. Here it collects 1/(2n) units of fuel, which is just enough fuel to return to base.
On each of the subsequent n − 2 trips the jeep collects 1/(2n − 2) units of fuel from this second fuel dump on the way out, so that it leaves the fuel dump carrying 1 unit of fuel. It also collects 1/(2n − 2) units of fuel from the second fuel dump on the way back, which is just enough fuel to return to the first fuel dump.
The jeep continues in this way, so that on trip k it establishes a new kth fuel dump at a distance of 1/(2n − 2k + 2) units from the previous fuel dump and leaves (n − k)/(n − k + 1) units of fuel there. On each of the subsequent n − k trips it collects 1/(2n − 2k + 2) units of fuel from the kth dump on its way out and another 1/(2n − 2k + 2) units of fuel on its way back.

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

1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{n}}=\sum _{k=1}^{n}{\frac {1}{k}}\equiv 2\times \mathrm {explore} (n)

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.

The distance travelled on the last trip is the nth harmonic number, H_n. 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

1+{\frac {1}{3}}+{\frac {1}{5}}+\cdots +{\frac {1}{2n-1}}=\sum _{k=1}^{n}{\frac {1}{2k-1}}=H_{2n-1}-{\frac {1}{2}}H_{n-1}\equiv \mathrm {cross} (n)

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.

Since

\mathrm {cross} (n)=\sum _{k=1}^{n}{\frac {1}{2k-1}}>\sum _{k=1}^{n}{\frac {1}{2k}}={\frac {1}{2}}H_{n}=\mathrm {explore} (n)

,

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

$\mathrm {explore} (n)={\frac {1}{2}}H_{n}={\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{6}}+\cdots +{\frac {1}{2n}}$ , for exploring the desert where the jeep must return to the base at the end of every trip;
$\mathrm {cross} (n)=H_{2n-1}-{\frac {1}{2}}H_{n-1}=1+{\frac {1}{3}}+{\frac {1}{5}}+\cdots +{\frac {1}{2n-1}}$ , for crossing the desert where the jeep must return to the base at the end of every trip except for the final trip, when the jeep travels as far as it can before running out of fuel.

Here $H_{n}=1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{n}}$ 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

\mathrm {explore} (n)=\int _{0}^{n}{\frac {\mathrm {d} f}{2\lceil n-f\rceil }}

with the first fuel dump located at $\{n\}/(2\lceil n\rceil )$ units of distance away from the starting base, the second one at $1/(2\lceil n\rceil -2)$ units of distance away from the first fuel dump, the third one at $1/(2\lceil n\rceil -4)$ units of distance away from the second fuel dump, and so on. Here $\{n\}=n-\lfloor n\rfloor$ is the fractional part of $n$ .

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

\mathrm {cross} (n)=\int _{0}^{n}{\frac {\mathrm {d} f}{2\lceil n-f\rceil -1}}

with the first fuel dump located at $\{n\}/(2\lceil n\rceil -1)$ units of distance away from the starting base, the second one at $1/(2\lceil n\rceil -3)$ units of distance away from the first fuel dump, the third one at $1/(2\lceil n\rceil -5)$ units of distance away from the second fuel dump, and so on. Here $\{n\}=n-\lfloor n\rfloor$ is the fractional part of $n$ .

Order independence

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/(2 n)$ units of fuel available. The $1/(2 n)$ 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."^[6]

(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.)

Related Research Articles

In physics, the cross section is a measure of the probability that a specific process will take place in a collision of two particles. 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.

A histogram is a visual representation of the distribution of quantitative data. To construct a histogram, the first step is to "bin" the range of values— 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) are adjacent and are typically of equal size.

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. The radius of gyration has dimensions of distance [L] or [M⁰LT⁰] and the SI unit is the metre (m).

In mathematics, 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 smallest integer greater than or equal to $x$ , denoted $⌈ x ⌉$ or $ceil(x)$ .

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

In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series. Generating functions are often expressed in closed form, by some expression involving operations on the formal series.

The Friedmann–Lemaître–Robertson–Walker metric is a metric based on an exact solution of the Einstein field equations of general relativity. The metric describes a homogeneous, isotropic, expanding universe that is path-connected, but not necessarily simply connected. The general form of the metric follows from the geometric properties of homogeneity and isotropy; Einstein's field equations are only needed to derive the scale factor of the universe as a function of time. Depending on geographical or historical preferences, the set of the four scientists – Alexander Friedmann, Georges Lemaître, Howard P. Robertson and Arthur Geoffrey Walker – are variously grouped as Friedmann, Friedmann–Robertson–Walker (FRW), Robertson–Walker (RW), or Friedmann–Lemaître (FL). This model is sometimes called the Standard Model of modern cosmology, although such a description is also associated with the further developed Lambda-CDM model. The FLRW model was developed independently by the named authors in the 1920s and 1930s.

A hexagonal number is a figurate number. The nth hexagonal number h_n is the number of distinct dots in a pattern of dots consisting of the outlines of regular hexagons with sides up to n dots, when the hexagons are overlaid so that they share one vertex.

In mathematics, the double factorial of a number $n$ , denoted by $n ‼$ , is the product of all the positive integers up to $n$ that have the same parity as $n$ . That is,

<span class="mw-page-title-main">Butterworth filter</span> Type of signal processing filter

The Butterworth filter is a type of signal processing filter designed to have a frequency response that is as flat as possible in the passband. It is also referred to as a maximally flat magnitude filter. It was first described in 1930 by the British engineer and physicist Stephen Butterworth in his paper entitled "On the Theory of Filter Amplifiers".

In mathematics, the Riemann–Liouville integral associates with a real function $another function Iαf of the same kind for each value of the parameter α > 0. The integral is a manner of generalization of the repeated antiderivative of f in the sense that for positive integer values of α, Iαf is an iterated antiderivative of f of order α. The Riemann–Liouville integral is named for Bernhard Riemann and Joseph Liouville, the latter of whom was the first to consider the possibility of fractional calculus in 1832. The operator agrees with the Euler transform, after Leonhard Euler, when applied to analytic functions. It was generalized to arbitrary dimensions by Marcel Riesz, who introduced the Riesz potential.$

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.

The Engel expansion of a positive real number x is the unique non-decreasing sequence of positive integers $such that$

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:

if a ≤ b and b ≤ c then a ≤ c (transitivity)
for all a and b, a ≤ b or b ≤ a (connexity).

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 that studies the discrepancy of general set systems.

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 statistics, the generalized Marcum Q-function of order $is defined as$

Scott's rule is a method to select the number of bins in a histogram. Scott's rule is widely employed in data analysis software including R, Python and Microsoft Excel where it is the default bin selection method.

References

1 2 3 Weisstein, Eric W. "Jeep Problem". MathWorld .
↑ Gardner, Martin (1994). My Best Mathematical and Logic Puzzles . Dover. pp. 53. ISBN 0-486-28152-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.
↑ Problems to Sharpen the Young, John Hadley and David Singmaster, The Mathematical Gazette, 76, #475 (March 1992), pp. 102–126.
↑ Optimal Logistics for Expeditions: the Jeep Problem with Complete Refilling, Gunter Rote and Guochuan Zhang, June 1996
↑ Fog of War transcript, www.errolmorris.com

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[wolfram-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.

[coxeter-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.

[a-4] Problems to Sharpen the Young, John Hadley and David Singmaster, The Mathematical Gazette, 76, #475 (March 1992), pp. 102–126.

[5] Optimal Logistics for Expeditions: the Jeep Problem with Complete Refilling, Gunter Rote and Guochuan Zhang, June 1996

[6] Fog of War transcript, www.errolmorris.com

[1]

[2]

[3]

[4]

[5]

[6]