Jeep problem

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.

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.

More complex variations on the problem have been proposed in which the fuel can only be left or collected in discrete amounts.

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

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.

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.

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.

After leaving the farthest fuel dump it travels a further distance of 1 unit.

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.

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.

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

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