Jeep problem
Encyclopedia
The jeep problem, desert crossing problem or exploration problem is a mathematics problem in which a jeep
must maximise 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 was solved by N. J. Fine
in 1947.
In either case the objective is to maximise the distance travelled 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.
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.
A strategy that maximises the distance travelled 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 travelled into the desert is half of this). 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, 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 travelled.
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. 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 travelled.
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:
(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.)
Jeep
Jeep is an automobile marque of Chrysler . The first Willys Jeeps were produced in 1941 with the first civilian models in 1945, making it the oldest off-road vehicle and sport utility vehicle brand. It inspired a number of other light utility vehicles, such as the Land Rover which is the second...
must maximise 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 was solved by N. J. Fine
Nathan Fine
Nathan Jacob Fine was a mathematician who worked on basic hypergeometric series. He is best known for his lecture notes on the subject which for four decades served as an inspiration to experts in the field until they were finally published as a book...
in 1947.
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 maximise the distance travelled 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.
In the classic problem the fuel in the jeep and at fuel dumps is treated as a continuous
Continuous function
In mathematics, a continuous function is a function for which, intuitively, "small" changes in the input result in "small" changes in the output. Otherwise, a function is said to be "discontinuous". A continuous function with a continuous inverse function is called "bicontinuous".Continuity of...
quantity. More complex variations on the problem have been proposed in which the fuel can only be left or collected in discrete amounts.
Solution
- 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
units on its final trip (the maximum distance travelled into the desert is half of this). 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 "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. 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 travelled.
Practical applications
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 IIWorld War II
World War II, or the Second World War , was a global conflict lasting from 1939 to 1945, involving most of the world's nations—including all of the great powers—eventually forming two opposing military alliances: the Allies and the Axis...
by B-29s, Robert McNamara
Robert McNamara
Robert Strange McNamara was an American business executive and the eighth Secretary of Defense, serving under Presidents John F. Kennedy and Lyndon B. Johnson from 1961 to 1968, during which time he played a large role in escalating the United States involvement in the Vietnam War...
says in the film The Fog of War
The Fog of War
The Fog of War: Eleven Lessons from the Life of Robert S. McNamara is a 2003 American documentary film about the life and times of former U.S. Secretary of Defense Robert S. McNamara as well as illustrating his observations of the nature of modern warfare...
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
Island hopping
Island hopping is a term that refers to the means of crossing an ocean by a series of shorter journeys between islands, as opposed to a single journey directly across the ocean to the destination.- Forms :...
strategy:
(The atomic bombing missions
Atomic bombings of Hiroshima and Nagasaki
During the final stages of World War II in 1945, the United States conducted two atomic bombings against the cities of Hiroshima and Nagasaki in Japan, the first on August 6, 1945, and the second on August 9, 1945. These two events are the only use of nuclear weapons in war to date.For six months...
at the end of World War II were flown using B-29 Superfortresses from the Pacific
Pacific Ocean
The Pacific Ocean is the largest of the Earth's oceanic divisions. It extends from the Arctic in the north to the Southern Ocean in the south, bounded by Asia and Australia in the west, and the Americas in the east.At 165.2 million square kilometres in area, this largest division of the World...
island of Tinian
Tinian
Tinian is one of the three principal islands of the Commonwealth of the Northern Mariana Islands.-Geography:Tinian is about 5 miles southwest of its sister island, Saipan, from which it is separated by the Saipan Channel. It has a land area of 39 sq.mi....
in the Northern Marianas Islands.)