Jeep Problem - Solution

Solution

A strategy that maximises the distance travelled 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

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