Crossing desert with smallest amount of water [duplicate]

Question

A man who lives in a desert sends his servant out to collect the flag which is 4 miles away from the man's home. To survive the servant must drink 1 litre of water on every mile he walks (so the amount of water is proportional to the distance walked). He can only carry 5 litres all at once. To do so he can leave caches of water at any time he wants. If we assume there is an infinite amount of water at the man's home how can the servant walk 4 miles to the flag, collect it and get back without dying and drinking as few liters of water as possible? Wanted is the smallest amount of water in litres that is needed to do this.

The alleged solution is 11.5 litres but I don't understand how to only use this amount because my friends and I showed that the minimum is 12 so I'm confused.

Answer 1

This puzzle is similar to the standard desert crossing puzzle, except that after you cross over, you then need to return to the origin. Because of this difference, you can leave water caches to be used on the return trip, which makes the solution a bit different from the standard puzzle.

You can solve this particular puzzle in 11.5 liters in this way:

1. Fill up 5 liters, walk 0.25 miles, drop 4.5 liters, walk back 0.25 miles.
2. Fill up 5 liters, walk 0.25 miles, drop 4.5 liters, walk back 0.25 miles.

10 liters have been used with the situation looking like this:

0* 25 50 75 100 125 150 175 200 225 250 275 300 325 350 375 400
900 flag

(Distance in .01 mile units)
(Water cache in .01 liter units)
(* = your location)

3. Fill up 1.5 liters (using 11.5 total), walk 0.25 miles, pick up 3.75 liters (full tank).

0 25* 50 75 100 125 150 175 200 225 250 275 300 325 350 375 400
525 flag

4. Walk 1.25 miles to the 1.5 mile mark, drop 2.5 liters, walk back 1.25 miles, pick up 5 liters (full tank).

0 25* 50 75 100 125 150 175 200 225 250 275 300 325 350 375 400
25 250 flag

5. Walk 1.25 miles to the 1.5 mile mark, pick up 1.25 liters (full tank).

0 25 50 75 100 125 150* 175 200 225 250 275 300 325 350 375 400
25 125 flag

6. Walk 2.5 miles to the 4 mile mark, pick up the flag, walk 2.5 miles back to the 1.5 mile mark (empty tank).

0 25 50 75 100 125 150* 175 200 225 250 275 300 325 350 375 400
25 125

7. Pick up 1.25 liters, walk 1.25 miles to the .25 mile mark, pick .25 liters, walk back to home base.

0* 25 50 75 100 125 150 175 200 225 250 275 300 325 350 375 400

How to solve:

To solve this puzzle, you can work backwards. You can see that you need 5 liters at the 1.5 mile mark to grab the flag and return (5 mile round trip). Assume that there was a previous 5 liter water cache at a distance N from the 1.5 mile mark. The optimal solution going from the previous cache to the 1.5 mile mark would be to go forward-drop-back-forward-pickup, where the drop is 2N water but N is picked up at the end, leaving N water at the 1.5 mile mark so that you can return to the previous cache on the way back. This f-b-f plus drop uses 4N water, so with capacity of 5 liters, 5 = 4N, or N = 5/4 = 1.25 miles.

(Note that in the standard version of the puzzle, you wouldn't leave any water there, so the distance would be N = 5/3 = 1.67 miles)

Now we know we need a cache of 5 liters at the 0.25 mile mark. Similar to the above, the optimal solution involves going f-b-f-b-f from the base and leaving an extra 0.25 liters at the cache. This uses 6*0.25 = 1.5 extra liters of water, in addition to the 10 liters being transported (5 for the cache and 5 for yourself), for a total of 11.5 liters.