When they say an army travels on its stomach, they mean you have to bring the food with you. I can't remember if I've asked this question before, so here you go... A little bit of logistics to wake you up on a Monday morning.
An explorer wishes to cross a barren desert that requires 6 days to cross, but one man can only carry enough food for 4 days. What is the fewest number of other men required to help carry enough food for him to cross?
I think I can do it with two helpers:
ReplyDeleteThe first travels for 1 day, leaves a 2-day cache, then returns.
The second travels for 1 day, fills up from the cache, travels another day, leaves a second 2-day cache, travels back for a day, picks up the rest of the food from the first cache, and returns.
There is now a 2-day cache of food 2 days from the start, which is just enough to let the traveller complete his journey.
If we're required to only have one trip then only one helper is required (as we only need enough food for the explorer to cross). Send both the explorer and our helper out with fully laden backpacks, they both share the helpers food for 2 days. The helper then goes for a walk a la Captain Oates and our intrepid and courageous explorer has 4 days worth of food and four days worth of travelling.
ReplyDeleteAlternatively if more than one trip is allowed, using Jon's method above (if our explorer isn't lazy) we can use no helpers by sending out the explorer to do the helper's food storage job.
Finally, if no-one can die and we must complete the trip in one go, 2 helpers are required. If we call our helpers something original like Helper A and Helper B then it may help the explanation:
All 3 pioneers share Helper A's food for day 1, leaving him with enough food for 1 days travel, 1 day from the start point, leaving him free to return safely, content in the knowledge of a job well done.
On day two, the two remaining fellows of nomadic persuasion share Helper B's food, leaving him with enough food for two days travel, two days from the start point, again leaving him free to return home on a full stomach.
This then leaves our explorer with 4 days worth of food, 4 days from the other side of the barren dessert, so provided he doesn't get eaten by anything he'll make the other side.
Rich - great points. I'd completely ignored the 'disposable helpers' alternative, which may say something good about my ethics, or may just mean that I wasn't being ruthless enough! On the other hand I believe we don't lose (or gain) any generality by having separate journeys compared with everyone setting out at the same time, although you are right that by doing so we trade 'journeys' for 'helpers'.
ReplyDeleteThis problem is nagging me to try to consider the more general case where one person can carry i days worth of food, and the desert takes j days to cross. I'm sure that this is a problem that has already been solved thousands of times out there on the internet, though (in particular, this feels very similar to a problem involving aeroplanes that I've seen in the past).
I have nothing to add to your solutions, but you have made me curious about the general problem. I've seen this type of problem for years, but I never saw any theory on it.
ReplyDeleteBTW, I was assuming you all had the ethics to keep your explorers alive! ;-)