r***@gmail.com

2016-02-10 19:06:53 UTC

Permalink

You are stranded in a desert, at a base station,Raw Message

looking to get home. There's a rescue truck,

11 miles away. Along the route, there is a

series of rest stations, one at each mile.

To make this long trip, you need water. You

have a wagon, which can carry up to 7 liters.

You drink one liter of water during the hike

between each station, forward or backward

Clearly, you cannot make it in one shot. However,

you may store any quantity of water at the rest

stations. Hence the solution: a series of hikes,

back and forth,dropping and picking up water, until

you ultimately arrive at the rescue point.

What is the minimum initial quantity of water required,

at the base?

This case isn't hard, as 11 miles is a short

distance. But imagine it's 20 to the rescue station,

that would be a lot of work!

Note the problem statement: not merely to find

a procedure to reach safety, but also minimizing

the store of water. So, for a long walk, you

could find an algorithm solution; but how would

you show your algorithm is optimal?

--

Rich