All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Exploring New Guinea (based on a true story!) (Posted on 2009-05-07) Difficulty: 2 of 5

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.)

See The Solution Submitted by FrankM    
Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Going farther with less (spoiler) | Comment 1 of 2
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
  Posted by Steve Herman on 2009-05-07 15:27:51

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (1)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (6)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information