- the answer is
rem = (50 n) mod 60
m = (50 n - rem) / 60
A much harder problem occurs when the truck can siphon gas, but if it does, it must siphon the gas into one of the initial barrels.
Here is a table with the amounts of gas that pass the depot sites, the optimal locations of the depot sites, and the amounts of gas to have in the tank as one leaves the depot sites on the outbound trip, for the 50-gallon drum, 10 MPG, 10-gallon tank, for the limited cache problem. An optimal solution is obtained by working from the finish, back, and using multiple trucks as detailed below. The algorithm which produced the table is also provided.
The table is read diagonally from bottom to top beginning with the row with the proper gas amount. Start with the trip 1 column, and fill the tank to the designated amount, proceed to the location in the distance column for one row up, and leave a full drum. Continue with the trip 2 column for the beginning row, fill the truck to the designated amount, proceed up one row and over one column to the trip 1 column, fill the tank to the designated amount, proceed to the location in the distance column for another row up, and leave a full drum. For trips 3 to n start in the appropriate column and move up and over until you reach the distance column and leave the drum. If a truck arrives at a depot site with more gas than the table amount, then no gas is added. Gas is never removed. On return trips, the tank is only filled with enough gas to reach the next depot site.
Since the drum and tank capacities and mileage are rational numbers, all the table entries could be expressed precisely as rational numbers, e.g., Row 3 is
The solutions all result in 6 full drums a distance 1076.9264 from the end, and a truck with 5 Gallons in the tank. The rest of the solution is the same as the unlimited cache solution. The distances obtained for 419 1/11 Gallons or less are the same as the unlimited cache problem solutions. Once the depot sites are over 1/2 of a tank apart the limited and unlimited solutions converge. The key to finding cache-limited solutions is to realize that gas stored in the tank beyond what is necessary for the return trip is only useful if the truck continues on past the previously established depot sites.
Here are some examples of how to use the table to construct solutions:
Given 26 full barrels and one partially full barrel with 7.0368 Gallons in it (for a total of 1307.0368 Gallons), one sees that the optimal distance is 1511.0149 Miles. There will be 19 (17+1+1) trips starting with full gas tanks, and 3 trips with partially full tanks. A total of 22 drums will be moved from the start, using 21 round trips and one one-way trip.
Trip 1 will take a total of 2.750205 Gallons from drums 23-27, and take drum 22 13.7511 miles and return.
Trip 3 will take a total of 8.658458 Gallons from drums 23-27, and take drum 20 43.2923 miles and return.
Notice that this trip does not use any gas from drums 21 or 22.
Trip 6 will take a total of 10 Gallons from drums 23-27, 2.750205 Gallons from drum 22, 2.877949 Gallons from drum 21, 3.030303 Gallons from drum 20, and 0.199293 [=3.212949-(10-6.986344)?] from drum 19, no gas from drum 18 and take drum 17 a total of 94.2888 miles and return.
Trip 21 will fill up at every depot site on the way up, leave drum 2 at 1076.9624, and take just enough gas from each site to return to the next one.
Trip 22 will empty all the drums as it passes and end up at 1076.9264 with 6 full drums and 5 Gallons of gas in the tank.
Check on gas use at a depot site:
The total gas taken from drum 19 is 0.199293+(15+0.5)*3.212949=50 Gallons.
If only 1306.038 Gallons were available, then the optimal distance decreases by 10*1/(21*2+1), and the starting gas amounts would decrease by 2/(21*2+1) for the first 21 trips and by 1/(21*1+1) for the last trip. No other rows need to be changed.
The gas amounts in the Trip 1 column are always the amounts to go to the next depot site and back.
The optimal distances can be obtained with other fueling schedules than those presented here. In particular, there is considerable flexibility in how to allot the gas at the start and at the first depot site.
Since the question is often posed in terms of optimal distance for a number of drums, the following table is provided.
Entries can be calculated from the first table. For example, for 19 drums,
Optimal Limited Cache Solutions for the General Case.
Cache and Ferry. (How far can a truck go in a desert?) A pick-up truck is in the desert beside N gas drums. Each drum is full and contains K units of gas. The truck's gas tank is empty and holds 1 unit of gas and the gets 1 unit of distance per unit of gas. The truck can carry one drum, whether full or empty, in its bed. How far away from the starting point can you drive the truck?
Consider the problem beginning at the end of the trip and try to find the minimum amount of gas that must pass any point. The backwards multiple-truck statement of the problem is as follows:
You are given a truck with an empty gas tank and an empty drum. At any time you may acquire another truck and drum. The first truck produces one unit of gas for every unit of distance traveled. Additional trucks produce two units of gas per unit of distance. The gas is created in the truck's gas tank. It may be removed and placed into any unfilled drum. No gas may be placed into a truck's gas tank and all gas must be placed somewhere. You cannot get rid of a truck unless you can place all of the gas in its tank and drum into other drums. Your objective is to have traveled as far as possible when the total gas in your caravan is N K.
The optimal strategy is clear:
Never take gas from a tank until it is full, i.e., you have to. Get a new truck and drum only when all current drums are full.
In other words, always drive as far as you possibly can before getting another truck and drum.
- current caravan must travel to have each of the following occur
- 1. D1 distance until the total gas in the caravan is N K. 2. D2 distance until all the available drums are full. 3. D3 distance until a partially full gas tank is filled.
- We must keep track of
- 1. NV number of vehicles=number of drums 2. NTPF number of partially full tanks 3. PD amount in the partially filled drum 4. PT(1,NTPF) amounts in partially filled tanks 5. GT total gas in the caravan 6. DT distance traveled to current stage
Determine the minimum of D1, D2, and D3; increment DT; and adjust the other variables as need (e.g., add another drum and truck if D2 was the minimum). Continue until GT = N K. Where we get new drums are depot sites and the PT amounts are the amounts of gas as we leave the sites.
Here is a program to find the values in the first table (or for any other drum and tank sizes and mileages).
-- firstname.lastname@example.org (Lawrence E. Flynn)
C.G. Phipps, The jeep problem : a more general solution, American Mathematical Monthly, 54, pp 458-62, (1947). Unlimited cache problem and solution.
G.G. Alway, Crossing the desert, Mathematical Gazette, 41(209), Note #2707 (1957). Half way across in one one load problem and solution.
The limited cache problem is the same as the "Desert Fox" problem described, but not solved, by A. K. Dewdney, July 1987, "Scientific American."
Dewdney's October 1987 Scientific American article gives for N=2, the optimal distance of 733.33 miles.
In the November issue, Dewdney lists the optimal distance of 860 miles for N=3, and gives a better, but not optimal, general distance formula.
- gives an even better formula, for which he incorrectly claims optimality
- The following shows that Westbrook's formula is not optimal for N=8