Jeep problem
   HOME

TheInfoList



OR:

The jeep problem, desert crossing problem or exploration problem"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 Walter William Rouse Ball (14 August 1850 – 4 April 1925), known as W. W. Rouse Ball, was a British mathematician, lawyer, and fellow at Trinity College, Cambridge, from 1878 to 1905. He was also a keen amateur magician, and the founding ...
and
H.S.M. Coxeter Harold Scott MacDonald "Donald" Coxeter, (9 February 1907 – 31 March 2003) was a British and later also Canadian geometer. He is regarded as one of the greatest geometers of the 20th century. Biography Coxeter was born in Kensington t ...
(1987). ''Mathematical Recreations and Essays'', Thirteenth Edition, Dover, p32. .
is a mathematics problem in which a
jeep Jeep is an American automobile marque, now owned by multi-national corporation Stellantis. Jeep has been part of Chrysler since 1987, when Chrysler acquired the Jeep brand, along with remaining assets, from its previous owner American Moto ...
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 The medieval Latin language, Latin manuscript ''Propositiones ad Acuendos Juvenes'' ( en, Problems to Sharpen the Young) is one of the earliest known collections of recreational mathematics problems.Alcuin Alcuin of York (; la, Flaccus Albinus Alcuinus; 735 – 19 May 804) – also called Ealhwine, Alhwin, or Alchoin – was a scholar, clergyman, poet, and teacher from York, Northumbria. He was born around 735 and became the student o ...
, with the puzzle being about a travelling camel eating grain.Problems to Sharpen the Young
John Hadley and David Singmaster, ''The Mathematical Gazette'', 76, #475 (March 1992), pp. 102–126.
The ''De viribus quantitatis'' (c. 1500) of
Luca Pacioli Fra Luca Bartolomeo de Pacioli (sometimes ''Paccioli'' or ''Paciolo''; 1447 – 19 June 1517) was an Italian mathematician, Franciscan friar, collaborator with Leonardo da Vinci, and an early contributor to the field now known as accounting ...
also discusses the problem. A modern treatment was given by N. J. Fine in 1947. Variations of the problem are the camel and bananas problem 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 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 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 A multistage rocket or step rocket is a launch vehicle that uses two or more rocket ''stages'', each of which contains its own engines and propellant. A ''tandem'' or ''serial'' stage is mounted on top of another stage; a ''parallel'' stage i ...
.


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 Continuity or continuous may refer to: Mathematics * Continuity (mathematics), the opposing concept to discreteness; common examples include ** Continuous probability distribution or random variable in probability and statistics ** Continuous ...
quantity. More complex variations on the problem have been proposed in which the fuel can only be left or collected in discrete amounts.Optimal Logistics for Expeditions: the Jeep Problem with Complete Refilling
Gunter Rote and Guochuan Zhang, June 1996
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

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/(2''n'') units and leaves (''n'' − 1)/''n'' units of fuel at a fuel dump. The jeep still has 1/(2''n'') units of fuel – just enough to return to base. *On each of the subsequent ''n'' − 1 trips the jeep collects 1/(2''n'') 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/(2''n'') 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/(2''n'' − 2) units and leaves (''n'' − 2)/(''n'' − 1) units of fuel at a second fuel dump. The jeep still has 1/(2''n'' − 2) units of fuel, which is just enough to return to the first fuel dump. Here it collects 1/(2''n'') units of fuel, which is just enough fuel to return to base. *On each of the subsequent ''n'' − 2 trips the jeep collects 1/(2''n'' − 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/(2''n'' − 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 ''k''th fuel dump at a distance of 1/(2''n'' − 2''k'' + 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/(2''n'' − 2''k'' + 2) units of fuel from the ''k''th dump on its way out and another 1/(2''n'' − 2''k'' + 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 + \frac + \cdots + \frac = \sum_^n \frac \equiv 2\times\mathrm(n) units on its final trip (the maximum distance traveled 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 ''n''th
harmonic number In mathematics, the -th harmonic number is the sum of the reciprocals of the first natural numbers: H_n= 1+\frac+\frac+\cdots+\frac =\sum_^n \frac. Starting from , the sequence of harmonic numbers begins: 1, \frac, \frac, \frac, \frac, \dot ...
, ''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 ''k''th fuel dump at a distance of 1/(2''n'' − 2''k'' + 1) units from the previous fuel dump and leaves (2''n'' − 2''k'' − 1)/(2''n'' − 2''k'' + 1) units of fuel there. On each of the next ''n'' − ''k'' − 1 trips it collects 1/(2''n'' − 2''k'' + 1) units of fuel from the ''k''th dump on its way out and another 1/(2''n'' − 2''k'' + 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/(2''n'' − 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 + \frac + \cdots + \frac = \sum_^n \frac=H_-\fracH_ \equiv \mathrm(n) 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 :\mathrm(n)=\sum_^n \frac > \sum_^n \frac = \fracH_=\mathrm(n) 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 * \mathrm(n)= \fracH_=\frac + \frac + \frac + \cdots + \frac, for exploring the desert where the jeep must return to the base at the end of every trip; * \mathrm(n)=H_-\fracH_=1 + \frac + \frac + \cdots + \frac , 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 + \frac + \cdots + \frac'' is the nth
harmonic number In mathematics, the -th harmonic number is the sum of the reciprocals of the first natural numbers: H_n= 1+\frac+\frac+\cdots+\frac =\sum_^n \frac. Starting from , the sequence of harmonic numbers begins: 1, \frac, \frac, \frac, \frac, \dot ...
.


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 units of fuel is :\mathrm(n) = \int_0^n \frac with the first fuel dump located at \/(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-\lfloor n \rfloor is the fractional part of . The maximum distance achievable for the "cross the desert" problem with units of fuel is :\mathrm(n) = \int_0^n \frac with the first fuel dump located at \/(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-\lfloor n \rfloor is the fractional part of .


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 m> \mathrm(n)=1/15+1/3+1, no solution exists for this problem; * If m\leq \mathrm(n)-\mathrm(\lfloor n\rfloor)=1/15, no midway camp post is necessary for the transport, and the distance ''m'' will be repeated for 2 \lceil n \rceil-1=5 times by the camel, so the maximum amount of bananas tranported to the market is n-m\times (2 \lceil n \rceil-1)=7/3-5m; * If \mathrm(n)-\mathrm(\lfloor n\rfloor), the optimal solution to transport that maximum amount of bananas requires some midway camp posts: *# For ''m=1/4<(1/3+1/15)'', only one midway camp post is necessary at a distance of 1/15 units away from the starting base, where a total of 2 units of bananas will accrue. The distance from the camp post to the market is (1/4-1/15), which will be repeated 3 times by the camel, and the maximum amount of bananas tranported to the market is 2-(1/4-1/15)*3=1.45 units; *# For ''m=1/2>(1/3+1/15)'', another midway camp post is necessary at a distance of 1/3 units from the first camp post, where a total of 1 unit of bananas will accrue. The distance from the second camp post to the market is /2-(1/3+1/15) which will be traveled only once by the camel, and the maximum amount of bananas tranported to the market is 1- /2-(1/3+1/15)1=0.9 units. If the camel is required to eventually return to the starting base, then the \mathrm(n) function applies (still assuming ''n=7/3''): *If m> \mathrm(n)=1/18+1/4+1/2, no solution exists for this problem; * If m\leq \mathrm(n)-\mathrm(\lfloor n\rfloor)=1/18, no midway camp post is necessary for the transport, and the distance ''m'' will be repeated for 2 \lceil n \rceil=6 times by the camel, so the maximum amount of bananas tranported to the market is n-m\times (2 \lceil n \rceil)=7/3-6m; * If \mathrm(n)-\mathrm(\lfloor n\rfloor), the optimal solution to transport that maximum amount of bananas requires some midway camp posts: *# For ''m=1/4<(1/4+1/18)'', only one midway camp post is necessary at a distance of 1/18 units away from the starting base, where a total of 2 units of bananas (plus 1/18 units for the camel's final return) will accrue. The distance from the camp post to the market is (1/4-1/18), which will be repeated 4 times by the camel, and the maximum amount of bananas tranported to the market is 2-(1/4-1/18)*4=1.22 units; *# For ''m=1/2>(1/4+1/18)'', another midway camp post is necessary at a distance of 1/4 units from the first camp post, where a total of 1 unit of bananas (plus 1/4 units for the camel's final return) will accrue. The distance from the second camp post to the market is /2-(1/4+1/18) which will be repeated twice by the camel, and the maximum amount of bananas tranported to the market is 1- /2-(1/4+1/18)2=0.61 units. 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 :\mathrm(n)=\frac+1=2-\frac 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 :\mathrm(n)=\frac=1-\frac 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 ''n''th
harmonic number In mathematics, the -th harmonic number is the sum of the reciprocals of the first natural numbers: H_n= 1+\frac+\frac+\cdots+\frac =\sum_^n \frac. Starting from , the sequence of harmonic numbers begins: 1, \frac, \frac, \frac, \frac, \dot ...
: :''H_n=1 + \frac + \frac + \cdots + \frac'' 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 round-trips between the base and the first fuel dump, leaving units of fuel at the fuel dump each time and then make an -th trip one-way to the first fuel dump, thus arriving there with a total of units of fuel available. The units are saved for the return trip to base at the very end and the other units of fuel are used to move fuel between the first and second fuel dump, using round-trips and then an -th trip one-way to the second fuel dump. And so on.


Practical applications

The problem can have a practical application in wartime situations, especially with respect to
fuel efficiency Fuel efficiency is a form of thermal efficiency, meaning the ratio of effort to result of a process that converts chemical potential energy contained in a carrier (fuel) into kinetic energy or work. Overall fuel efficiency may vary per device, wh ...
. In the context of the bombing of Japan in
World War II World War II or the Second World War, often abbreviated as WWII or WW2, was a world war that lasted from 1939 to 1945. It involved the vast majority of the world's countries—including all of the great powers—forming two opposin ...
by
B-29 The Boeing B-29 Superfortress is an American four-engined propeller-driven heavy bomber, designed by Boeing and flown primarily by the United States during World War II and the Korean War. Named in allusion to its predecessor, the B-17 Fly ...
s,
Robert McNamara Robert Strange McNamara (; June 9, 1916 – July 6, 2009) was an American business executive and the eighth United States Secretary of Defense, serving from 1961 to 1968 under Presidents John F. Kennedy and Lyndon B. Johnson. He remains the Lis ...
says in the film ''
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 McNamara, illustrating his observations of the nature of modern warfa ...
'' 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 Leapfrogging, also known as island hopping, was a military strategy employed by the Allies in the Pacific War against the Empire of Japan during World War II. The key idea is to bypass heavily fortified enemy islands instead of trying to captu ...
strategy: (The atomic bombing missions at the end of World War II were flown using B-29
Superfortresses The Boeing B-29 Superfortress is an American four-engined Propeller (aeronautics), propeller-driven heavy bomber, designed by Boeing and flown primarily by the United States during World War II and the Korean War. Named in allusion to its p ...
from the
Pacific The Pacific Ocean is the largest and deepest of Earth's five oceanic divisions. It extends from the Arctic Ocean in the north to the Southern Ocean (or, depending on definition, to Antarctica) in the south, and is bounded by the continen ...
island of
Tinian Tinian ( or ; old Japanese name: 天仁安島, ''Tenian-shima'') is one of the three principal islands of the Commonwealth of the Northern Mariana Islands. Together with uninhabited neighboring Aguiguan, it forms Tinian Municipality, one of th ...
in the
Northern Marianas Islands The Northern Mariana Islands, officially the Commonwealth of the Northern Mariana Islands (CNMI; ch, Sankattan Siha Na Islas Mariånas; cal, Commonwealth Téél Falúw kka Efáng llól Marianas), is an unincorporated territory and commonwea ...
.) See also
Operation Black Buck Operations Black Buck 1 to Black Buck 7 were seven extremely long-range ground attack missions conducted during the 1982 Falklands War by Royal Air Force (RAF) Vulcan bombers of the RAF Waddington Wing, comprising aircraft from 44, 50 and ...
for an application of these ideas. In these missions, conducted during the
Falklands War The Falklands War ( es, link=no, Guerra de las Malvinas) was a ten-week undeclared war between Argentina and the United Kingdom in 1982 over two British dependent territories in the South Atlantic: the Falkland Islands and its territorial de ...
, the
Royal Air Force The Royal Air Force (RAF) is the United Kingdom's air and space force. It was formed towards the end of the First World War on 1 April 1918, becoming the first independent air force in the world, by regrouping the Royal Flying Corps (RFC) and ...
used air to air refueling by staging tankers to enable the
Vulcan Vulcan may refer to: Mythology * Vulcan (mythology), the god of fire, volcanoes, metalworking, and the forge in Roman mythology Arts, entertainment and media Film and television * Vulcan (''Star Trek''), name of a fictional race and their home p ...
bombers based on
Ascension Island Ascension Island is an isolated volcanic island, 7°56′ south of the Equator in the South Atlantic Ocean. It is about from the coast of Africa and from the coast of South America. It is governed as part of the British Overseas Territory o ...
to bomb targets in the
Falkland Islands The Falkland Islands (; es, Islas Malvinas, link=no ) is an archipelago in the South Atlantic Ocean on the Patagonian Shelf. The principal islands are about east of South America's southern Patagonian coast and about from Cape Dubouzet ...
.


See also

* Harmonic series (mathematics) *
Optimization (mathematics) Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...


References

{{reflist Mathematical optimization Recreational mathematics Logic puzzles