In the days before the invention of aeroplanes European explorers faced grave difficulties exploring the foodless and nearly impenetrable jungles of New Guinea.

With time and experience, they learnt that a well trained and physically fit explorer could carry a three days supply of food with him.

Show how a team of 3^N-1 explorers could send one of their number a distance N days march from the base camp, with all explorers returning safely to the base camp. (Note that once an explorer returns to camp, he must stay there.)

Well, I think we can do a lot better than this.  The problem suggests that 1 person can go as far as a day out, 3 persons can send an explorer 2 days out, 9 persons can send an explorer 3 days out, etc.

In fact, I think 1 person can go as far as a 1.5 days out, 3 persons can send an explorer 2.25 days out, 9 persons can send an explorer 4.243452 days out, etc.

Here's how.  Let E = the number of explorers.

a) E = 1.  Hikes and turns around when his pack is half-empty (after 1.5 days).  Call the point where he turns around checkpoint 1.

b) E = 2   Both persons set out and walk, eating out of the pack of the second explorer.  When his pack is half-empty (after 3/4 of a day), The second explorer buries 3/4 of a day of food at a location we will call checkpoint 2, and hikes back to base camp with 3/4 of a day of food.  The first explorer keeps walking another 1.5 days, turns around, digs up 3/4 of a day of food at checkpoint 2, and hikes back to camp.

c) E = 3   Three explorers set out together, eating out of the pack of the third explorer. When his pack is half empty, The 3rd explorer buries 1 day of food (enough for the other two to get from this point back to camp) at checkpoint 3, and returns to camp with 1/2 a day of food. The remaining two act as if they were just starting out, and walk another 3/4 days.  Explorer two buries 3/4 of a day of food at checkpoint 2, walks 3/4 of a day back to checkpoint 3, digs up 1/2 a day of food, leaves the other half for explorer 1, and walks back to camp.  Explorer 1 hikes another day and a half, turns around, digs up 3/4 of a day of food at checkpoint 2, walks 3/4 of a day, digs up half a day of food at checkpoint 3, and returns to base camp.  Explorer one has gone 3/2 + 3/4 + 3/6 days out = 2.25 days.

IN GENERAL) E = k.  k explorers set together, eating from the pack of the kth explorer.  When his pack is half empty (after 3/2k days), the kth explorer buries 3(k-1)/2k days work of food (at checkpoint k) and walks back to the previous checkpoint (in this case base camp) with the remaining 3/2k days worth of food.  Each of the remaining (k-1) explorers will eventually return to checkpoint k and take the 3/2k days of food they need to return to base camp.

The remaining k-1 explorers continue on, eating from the pack of the (k-1)st explorer.  When his pack is half empty (after 3/2(k-1) days), the (k-1)st explorer buries 3(k-1)/2k days work of food (at checkpoint k-1) and walks back to the previous checkpoint (checkpoint k) with the remaining 3/2(k-1).  Each of the remaining (k-2) explorers will eventually return to checkpoint k-1 and take the 3/2(k-1) days of food to that each will need get to checkpoint k.

  and so on.  and so on.

Explorer k turns back after 3/2(1/k) days

Explorer K-1 turns back after a total of 3/2(1/(k-1) + 1/k) days
           
Explorer 1 will travel 3/2*(1/1 + 1/2 + 1/3 + 1/4 + ... + 1/k) days, and then return, stopping at each checkpoint and taking just enough food to get him to the next checkpoint.

In total, k explorers travel the 3/2k days and back from checkpoint base camp to checkpoint k, consuming a total of 3 days of food.
          k-1 explorers traveled the 3/2(k-1) days from checkpoint checkpoint k to checkpoint k-1, consuming a total of 3 days of food.
          etc.

The kth explorer extends the maximum exploring distance by 3/2k days worth of marching.  In all cases, this is better than the problem suggests is possible.  The series 1/1, 1/2, 1/3 ... has an infinite sum, and is more closely associated with powers of 2 than with powers of 3.  Using methods outlined above, is seems like going slightly further than N days can be accomplished with 2^N-1 explorers, which quickly becomes a lot less than 3^N-1 explorers

Edited on May 7, 2009, 6:31 pm

Posted by Steve Herman on 2009-05-07 15:27:51