In the meantime, I'll be considering this logic problem. You should, too. It's a good one my professor showed me the other day. Been thinking about it on the subway on the daily.
Crossing the Desert
An unlimited supply of gasoline is available at one edge of a desert 800 miles wide, but there is no source on the desert itself. A truck can carry enough gasoline to go 500 miles (this will be called one "load"), and it can build up its own refueling stations at any spot along the way. These caches may be of any size, and it is assumed that there is no evaporation loss.
What is the minimum amount (in loads) of gasoline a truck will require in order to cross the desert? Is there a limit to the width of a desert the truck can cross?
(My Best Mathematical and Logic Puzzles, Martin Gardner, Dover 1994)
I've found a solution which uses four loads, but have yet to prove that it's optimal. If you get anything good, drop me a line.
2 responses to 3
I don't get the situation. Truck can carry 500 miles worth of gas. desert is 800 miles wide. What is the deal with setting up refueling stations? So can i go out 150 miles. Drop 200 miles worth of gas to chill. Then go back to base? And now i can use the 200 miles worth of gas next time I go to that cache?
I think you understand it just fine. The question could be phrased in terms of an actual volume of gas the truck can hold, but that just adds another level of calculation (miles per gallon, etc.) Phrased this way, you only have to deal with mileage and "miles worth" of gas.
Your situation is legit. If you go out 150 miles into the desert, you can drop off at most 200 gallons in order to have enough to get back out of the desert and refuel. Assume that the gas is left in some kind of storage tank that you can use later. When you get to the cache next time, you'll have 200 miles worth of gas waiting for you. You can fill up at any outpost, but your tank holds a maximum of 500 miles worth of gas. Exciting, right?
I still haven't been able to prove a best strategy. If you come up with something good, please let me know.
Post a Comment