21
$\begingroup$

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)

$\endgroup$
  • 1
    $\begingroup$ There's no limit on the water and the goal is to reduce the number of trips, it's not quite the same especially with the proof part, so voting to reopen. $\endgroup$ – Quark Jun 30 '15 at 3:00
  • 2
    $\begingroup$ A trip is one-way or two-way? $\endgroup$ – CodeNewbie Jun 30 '15 at 6:52
  • 2
    $\begingroup$ Probably it would be better to minimize the distance travelled, not the number of trips. IMO it would have more quantitative meaning. $\endgroup$ – Nejc Jun 30 '15 at 9:10
  • 1
    $\begingroup$ @IvoBeckers The distance you travel and the water you use are equal. # of refills, # of turnarounds, distance travelled, and water consumed all basically measure the same thing, I think. Consider caching and picking up water to be costless. $\endgroup$ – Aaron P Jun 30 '15 at 16:05
  • 1
    $\begingroup$ True but you also don't ask about distance $\endgroup$ – Ivo Beckers Jun 30 '15 at 16:06
12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm still trying to work through your solution, but I'll point out for now that @Noel appears to have a solution that requires fewer trips. puzzling.stackexchange.com/a/17171/13350 $\endgroup$ – Aaron P Jun 30 '15 at 16:21
  • $\begingroup$ My solution maximizes distance traveled per gallon of water used. it does not necessarily optimize number of one-way trips. Unless refilling along a trip is allowed, in which case it optimizes that ,as well. $\endgroup$ – user3294068 Jun 30 '15 at 16:33
  • $\begingroup$ Great solution!!! I had to work it all out to make sure it works, and it does! $\endgroup$ – Trenin Jun 30 '15 at 17:09
  • $\begingroup$ Wow, cool! I finally understood this after reading your first Update! I still don't understand the 4th paragraph though ("For N*10 gallons, you will need...") and I'm confused by the 5th paragraph ("For N=3 ..."). Why were 1/5 and 2/5 your "choices," and is it a typo that you say to cache 20 gallons at 2 miles (this exceeds your capacity)? Super cool solution, but the first few paragraphs are totally befuddling to me, and the last half makes perfect sense! : ) $\endgroup$ – Aaron P Jun 30 '15 at 19:05
  • $\begingroup$ The result ends up a lot like the Tsiolkovsky rocket equation, but with delta-x instead of delta-v, and discrete instead of continuous. $\endgroup$ – user2357112 Jul 1 '15 at 7:37
8
$\begingroup$

I think I found a faster way.

Divide the trip in 2'5 miles segments.

As @CodeNewbie said, we need 10 gallons on the 10 miles segment. Let's see how to do that.

0   2'5  5   7'5  10
---------------------
x    5
x    0   5
x    5   5
x    0   0   5
x    5   0   5
x    0   5   5
x    5   5   5
x    0   0   0   5

Each row represents a trip. On arriving to a segment, we either fill to 10 gallons, or leave 5 gallons. We have to repeat the process, and finally do the last trip.

That means that in 17 travels we'll be able to end up in the other side of the desert.

Under the same definition of travel that @CodeNewbie used, we'd need 33 travels, so it's still a better solution (assuming I didn't mess up)

$\endgroup$
  • 1
    $\begingroup$ Your diagram is good at showing the binary progression across the desert. Replace the 5's with 1's, reverse the image, and you're just counting. $\endgroup$ – Engineer Toast Jun 30 '15 at 13:12
  • $\begingroup$ The only mistake I see is that the 16th trip gets you across, not the 17th. $\endgroup$ – Joel Rondeau Jun 30 '15 at 13:46
  • $\begingroup$ Using your method, I think you can get across on the 11th trip if you deviate from the rule and just travel straight across picking up all the water on the way. $\endgroup$ – JS1 Jul 4 '15 at 2:42
7
$\begingroup$

Since keeping fractional amounts of water is possible, here's my solution (not sure if it's the most efficient). Here I have assumed that one trip constitutes movement in any one direction, forward or backward.

To be able to successfully complete this trip, we need to reach a situation where we have 10 gallons at the 10 mile mark.

Start with 10 gallons and carry it till 3.33 miles. 3.33 gallons are used up, cache 3.33 gallons and use the remaining 3.33 gallons to return to your origin. Repeat this 12 more times, till 43.33 gallons are collected at the 3.33 mile mark and you are back at the infinite well. (26 trips done so far)

In the 27th trip, when you reach the 3.33 mile mark, you have a total of 50 gallons now: 43.33 collected plus 6.66 carried. Refill your container to the full 10 gallons and move to the 6.66 mile mark. 3.33 gallons are used up, cache 3.33 gallons and use the remaining 3.33 gallons to return to the 3.33 mile mark. Repeat this 3 more times till 13.33 gallons are collected at the 6.66 mile mark and you are back at the 3.33 mile mark. (32 trips done so far, 40 gallons used up)

In the 35th trip, when you reach the 6.66 mile mark, you have a total of 20 gallons now: 13.33 collected plus 6.66 carried. Refill your container to the full 10 gallons and move to the 10 mile mark. 3.33 gallons are used up, cache 3.33 gallons and use the remaining 3.33 gallons to return to the 6.66 mile mark. Return, refill with the remaining 10 gallons, walk to the 10 mile mark, add the 3.33 gallons collected to your remaining 6.66 gallons, and use the 10 gallons to cross the desert.

To conclude,

the total number of trips I need is 37.

$\endgroup$
4
$\begingroup$

This can be optimized if we allow the water caches to be continuous. My answer requires 27 trips (one way):

This way we dont need 10 gallons at the 10 mile mark, but rather 10 gallons uniformly distributed over the first 10 miles (1 gallon / mile). Filling the first 3.33 miles requires 1 trip (both ways). Filling the next 3.33 miles requires 3 trips in total. Filling the final 3.33 miles (from 6.66 to 10) requires 9 trips. So filling the first 10 miles requires 9+3+1 = 13 trips (both ways). Together with the last trip it makes a total of 27 (one way) trips.

Visual representation of "linear water density" (gallons per mile) for each trip (each number represents 1/3 of a mile):

Miles __1__2__3__4__5__6__7__8__9__10
#1    1111111111
#2    2222222222
#3              1111111111
#4    11111111111111111111
#5    22222222221111111111 
#6              2222222222
#7    11111111112222222222     
#8    22222222222222222222
#9                        1111111111
#10   1111111111          1111111111
#11   2222222222          1111111111
#12             11111111111111111111
#13   111111111111111111111111111111
$\endgroup$
  • 1
    $\begingroup$ I don't understand step #1. You have ten gallons laid out, but what about the amount of water the guy needed to drink for that trip? That would have required six of those ten gallons. $\endgroup$ – default Jun 30 '15 at 13:39
  • $\begingroup$ @pauld Sorry, the answer was not clear enough. Each number represents 1/3 of a mile, so on the first trip you consume 3.33 gallons on each trip (go and back), and you lay the remaining 3.33 gallons along your path $\endgroup$ – Noel Jun 30 '15 at 14:21
  • 2
    $\begingroup$ Why do you need to distribute it uniformly? Simply drop $3.3$ gallons at each interval and you will get the same solution. $\endgroup$ – Trenin Jun 30 '15 at 16:31
3
$\begingroup$

Expanding on @Noel's answer because this is too big for a comment.

Why do you need to distribute the water uniformly? The following is the same number of trips.

1: Drop $3\frac{1}{3}$ gallons at the $3\frac{1}{3}$ mile marker.

2: Repeat #1. There are now $6\frac{2}{3}$ gallons t the $3\frac{1}{3}$ mile marker.

3: Drop $3\frac{1}{3}$ gallons at the $6\frac{2}{3}$ mile marker. Refresh from the first cache on the way out and on the way back.

4-6: Repeat 1-3. There is now $6\frac{2}{3}$ gallons at the $6\frac{2}{3}$ mile marker.

7/8: Repeat 1-2. There is now $6\frac{2}{3}$ gallons at both the $3\frac{1}{3}$ and $6\frac{2}{3}$ mile markers.

9: Drop $3\frac{1}{3}$ gallons at the $10$ mile marker. Refresh from the caches on the way out and on the way back.

10-12: Repeat 1-3. There is now $3\frac{1}{3}$ gallons at the $6\frac{2}{3}$ and $10$ mile markers.

13: Repeat 1. There is now $3\frac{1}{3}$ gallons at the $3\frac{1}{3}$, $6\frac{2}{3}$, and $10$ mile markers.

Final Tally

So, you've made 13 return trips (26-one way trips) to cache $3\frac{1}{3}$ gallons at the $3\frac{1}{3}$, $6\frac{2}{3}$, and $10$ mile markers.

One more one-way trip can get you to the $10$ mile mark with exactly $10$ gallons - enough to take you across the desert.

Notice that in terms of gallons of water (or equivalently, miles walked), this solution is equivalent to @Noel's solution, but also @CodeNewbie's. All three use $140$ gallons of water. The difference is that this solution and @Noel's optimize the number of trips. @CodeNewbie walks the same distance, but makes more shorter trips.

$\endgroup$
2
$\begingroup$

I found a better answer for this question which is

76.73

I am not sure the user who submitted this question is around to accept my answer but I found this question very interesting and solved it again. Then I noticed there is a $.218$ km extra distance with some extra water left.

The answer's methodology is actually the same as the original solver's one but this time it is optimized by using that $.218$ miles (actually more than that with second trick) and opportunity to drink enough water to move 1 mile without drinking from the cache of water at the beginning.

enter image description here

This is the old solution. You will notice that there is extra $.22$ miles so the solver claimed that it would be $80.00-0.22=79.78$ miles.

I will not explain the original methodology in detail again. But since there is extra around $.218$ miles at the end. We just need to substract that distance from the first part of the equation to save lots of distance and extra water on the way.

enter image description here

$\endgroup$
0
$\begingroup$

Solution to puzzle as currently defined:

Optimal 20 miles 20 gallons

In an alternating fashion, one container at a time, slide/carry each forward an arms reach distance while only walking forward. When the halfway point is reached carry the remainder of the water to the finish line.

General solution:

1gal/mile regardless of variable A

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.