mathematics - How much water do you need to cross the desert?

This question is inspired by Terry Pratchett's "Small Gods," in which an army crosses a vast desert by making multiple trips and caching water along the way.

1. Provide an answer.
2. I doubt I'm the first person to come up with this puzzle. Does anyone know of a "classic" puzzle like this, or know of a generic term for this puzzle?

The problem:
You are trying to cross a desert alone without dying of thirst. You know that for each mile you walk, you will need to drink exactly one gallon of water. You can carry at most 10 gallons of water on your person. The desert is 20 miles across. You obviously cannot cross the desert in one trip, but you can at any time leave a cache of water behind in the desert to pick up on a subsequent trip.

How can you cross the desert without dying of thirst?

and

Measured by distance walked, what is the optimal way to cross the desert?

Assume: You have an infinite supply of water/containers on the starting side. You can cache water in the desert without it evaporating. You can cache any fraction of the water you are carrying at any time. You will die instantly if you run out of water in the desert.

Bonus points for proof that your method is the best, or for a general solution where the desert length is a factor of a times longer than your one-time walking distance. (In the phrasing above, a=2)

Answer

Considering the general case, I attempt to answer the companion question: if you have $10 N$ gallons of water, how far can you get into the desert?

Obviously, for $N=1$, the answer is 10 miles.

For $N=2$, you carry the water distance $x$, drop off $(10-2x)$ gallons, and go back. Then you pick up the rest, go forward, refill at the cache, and continue on. This is obviously optimal$^1$ if the amount of water left to pick up is exactly the amount you used to get where you are. In other words, $x = 10/3$. At this point, you refill and continue, for a total of $10 (1 + \frac 13)$ miles.

For $N*10$ gallons, you will make $N-1$ round trips and one one-way trip. Thus, the water you use to move $x$ miles is $(2N-1)x$. This should be an even multiple of 10 gallons, or you are wasting water.

For $N=3$, you can pick either $x = \frac 15$ or $x = \frac 25$. In the first case, you cache 20 gallons of water 2 miles in. In the second, you cache 10 gallons of water 4 miles in. In the first case, you can make it $10 (1 + \frac 13 + \frac 15)$ miles, and in the second, you travel $10(1 + \frac 25)$ miles. The first option is clearly slightly better.

In general, for any $N$, you will want to make the next cache at $x = 1/(2N+1)$ miles. That uses up 10 gallons and you then continue with the next smaller $N$, which is more efficient. Making the caches farther in means you are using up your water on less efficient fractions.

Thus, with $10N$ gallons, you can travel as far as

$$10 \sum_{i=0}^{N-1} \frac 1 {2i+1} \text{miles.}$$

The smallest $N$ that makes it to 20 miles is $N=8$.

$$1 + \frac 13 + \frac 15 + \frac 17 + \frac 19 + \frac 1{11} + \frac 1{13} + \frac 1{15} = 2.02$$

Your total distance traveled is $79.8$ miles, and you have $0.2$ gallons left at the end.

This plan extends to any distance.

$^1$If you don't accept the "obviously optimal" comment above: If there are $10 N + \epsilon$ gallons at a cache point when you are ready to move forward, then you can make $N$ trips from there, and the $\epsilon$ gallons will be wasted. If there are $10 N - \epsilon$ gallons there, then when you go forward, you will be slightly short on your next leg. Making the cache slightly closer would cost you $\epsilon / (2N+3)$ distance on that leg, but gain you $\epsilon / (2N+1)$ on the next leg, for a net win.

Update I didn't count "trips" the same way everyone else does. Naively, this would take 64 trips, but if you optimized, each trip can go one cache further than the previous. I.e.,

• Trip 1, drop $10*{13\over 15}$ gallons at a distance $10*{1\over 15}$ miles.



• Trip 2, refill at the first cache as you pass it, then drop $10*{11\over 13}$ gallons at distance $10*{1\over 13}$ miles past first cache. When you pass the first cache on the way back, grab $10*{1\over 15}$ gallons needed to make it back to camp.


• Trip 3, refill at first two caches as you pass them, drop $10*{9\over 11}$ gallons at $10*{1\over 11}$ miles past second cache. Grab $10*{1\over13}$ and $10*{1\over 15}$ gallons at the second and first caches, respectively.


• Etc.

Thus, you can get all the way across in $15$ trips, assuming the trip-boundary is only when you change direction, not when you refill. If refilling counts as a trip-boundary, then this method will not yield the optimal number of trips.

Update 2 Rereading the question, I see what I should have been answering is "Measured by distance walked, what is the optimal way to cross the desert?" This solution definitely optimizes that, for a total of $79.8$ miles traveled.