In the Jeep problem in the desert is a famous puzzle logical-mathematical which tells us about resource optimization. The situation is this: a violent sandstorm has isolated us and ours three companions shipping in the middle of desert. The only way to save ourselves is to reach the nearest city, crossing hundreds of kilometers by car without any possibility of refueling at a petrol station along the way.
The problem, however, is that the four jeeps that still work have alimited autonomy: with a full tank they can only travel half the necessary distance. Luckily, the remaining jeeps are identical to each other, they all start with a full tank and can transfer fuel to each other.
Will we be able to get at least one jeep into the city, bringing the entire shipment to safety?
The solution to the jeep problem
We know that with a full tank every jeep can travel half the journey. This means that if we can get at least one jeep halfway through the journey with a completely full tank, we will be able to return to the city and we will be able to save the entire expedition. To do this, we will be forced to leave some cars in the desert: the task of the other jeeps at our disposal, in fact, will be to accompany the main car for a stretch of the route, transfer the own fuel and stop.
What, then, is the better strategy? When will we have to stop to transfer fuel? If we stop too late we will have consumed too much and there won’t be enough left to fill up; if we stop too soon, we won’t get to the halfway point with all the machines we need.
Since we have three cars “expendable”, a good strategy is to divide the first half of the path into three parts equal and to abandon a machine for each of these parts. The first stage, therefore, will be one sixth of the total journey, the second two sixths (or one third), the third three sixths (i.e. half).
To make sure this strategy works, we need to understand how much fuel we consume for each leg of the journey.
We know that to travel halfway you need a full tank, therefore:
To travel a certain portion of the route, we always need the double the fuel.
In other words:
- to travel half you need a tank for the journey entire;
- to travel a fourth of the journey is needed half reservoir;
- to travel a third of the journey are needed two thirds of the tank;
- to travel a sixth of the journey takes two sixths (i.e a third) of the tank.
At this point we can leave and start traveling the first long stretch of road a sixth of the total journey. After this first stretch, each of the four jeeps wore out a third of its own fuel and still has two thirds of the tank available.
So we decide to sacrifice machine number 4. We put a third of its total tank in machine 1 and a third in machine 2. In this way, both machine 1 and 2 have the tank full again, machine 4 is dry, while machine 3 still has the tank at two thirds. The driver of car 4 gets into car 1 and the three remaining cars drive off again.
The three cars continue for a sixth of the journey, thus arriving at two sixths (or a third) of the total road. All three cars have again consumed a third of the total tank remaining with two thirds (for machines 1 and 2) and a third for machine 3. Machine 3, therefore, sacrifices itself and transfers all the fuel left to jeep 1. Jeep 1 thus returns to having a full tank, while jeep 2 retains two thirds of the tank. The driver of Jeep 3 also boards Jeep 1 and the two remaining jeeps they leave again.
To reach the halfway point they still have to travel a sixth of the total distance. When they arrive at halfjeep 1 still has two thirds of the tank, while jeep 2 has the last third of fuel. Jeep 2 then transfers all the remaining fuel to Jeep 1, which ends up with the full tank exactly halfway along the route.
From here on the problem is solved: With a full tank and all the explorers on board, Jeep 1 can travel the second half of the desert and reach the destination.
These types of problems and riddles in which a means of transport must maximize the distance that can be traveled in hostile environments, using limited and difficult to find resources, are called “desert crossing problems“. They are studied and applied in logistics to optimize transport routes and reduce supply costs, but also in the military field to plan supply lines and ensure operational continuity in difficult territories. A similar idea also appears in the design of space rocket launches, where the tanks are released as they become empty, in order to optimize the weight of the rocket, a bit like the explorers who abandoned their jeeps in the middle of the desert.
