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 3N-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
2N-1 explorers, which quickly becomes a lot less than
3N-1 explorers
Edited on May 7, 2009, 6:31 pm