8
$\begingroup$

This is a problem I once found in a math textbook a tutor used with me.

A group of explorers is trying to get from their base camp to another camp which is eight days' walk through the desert.

However, each explorer can only carry five days' worth of supplies. How many explorers need to venture out to make sure that at least two of the explorers make it to the second camp and the rest make it safely back to base camp before being stranded without supplies?

This problem is somewhat similar to the camel transporting bananas puzzle, but this time there are multiple people who can exchange supplies between each other.

$\endgroup$
6
$\begingroup$

Six explorers, according to the following schedule:

Day 1: 6 explorers start with 28 rations and end with 22. Two return with 2 rations (1 per).

Day 2: 4 explorers start with 20 rations and end with 16. One returns with 2 rations.

Day 3: 3 explorers start with 14 rations and end with 11. One returns with 3 rations.

Day 4: 2 explorers start with 8 rations and end with 6.

Day 5: 2 explorers start with 6 rations and end with 4.

Day 6: 2 explorers start with 4 rations and end with 2.

Day 7: 2 explorers start with 2 rations and end with 0.

Could "almost" do this with 5 and just let them get a little hungry but the six is needed just for one meal. Note that there's no need to load everyone to max at the beginning since 4 explorers can only carry 20 meals.

UPDATE

As pointed out in comments, the solution above assumes that they eat at the end of the day (where day 8 should be "start with 0 and arrive hungry"). Below follows the rather similar solution for the more reasonable scenario of eat at the start or during the day.

Day 1: 8 explorers start with 40 rations and end with 32. Two return with 2 rations (1 per).

Day 2: 6 explorers start with 30 rations and end with 24. Two return with 4 rations (2 per).

Day 3: 4 explorers start with 20 rations and end with 16. Two return with 6 rations (3 per).

Day 4: 2 explorers start with 10 rations and end with 8.

Day 5: 2 explorers start with 8 rations and end with 6.

Day 6: 2 explorers start with 6 rations and end with 4.

Day 7: 2 explorers start with 4 rations and end with 2.

Day 8: 2 explorers start with 2 rations and end with 0.

This solution is more symmetrical, which feels better somehow.

$\endgroup$
  • $\begingroup$ As I read the problem, you need rations for the two crossers for day 8. $\endgroup$ – Ross Millikan May 19 '14 at 13:59
  • $\begingroup$ As with the camel-banana problem, the question is when the camel is fed and when the rations are used. If they're used at the end of the day, it's acceptable to start the eighth day with 0 rations, since the explorers will reach the other camp where rations are available. But if the rations are to be used during the day, you need to start day 8 with 2 rations left. $\endgroup$ – SQB May 20 '14 at 7:12
  • $\begingroup$ Good point about start/end of day. I really should have been more clear and written in day 8 where they eat at the end. I'll update with a version where they eat at the start or during the day ... which seems more reasonable anyway. $\endgroup$ – igelkott May 21 '14 at 6:48
3
$\begingroup$

Minimum Number of Explorers = 2

If food supplies can be stored along the route, only these two explorers are needed. The rules don't offer this as an option but they don't seem to disallow it either. Assuming a liberal interpretation, here's an alternate solution:

The two explorers load their packs and walk two days. They leave two rations at a suitable location, "camp 2", and return to the base on their remaining rations. This is repeated until the 8th trip where they instead walk three days to "camp 3", i.e., where they would be at the end of day 3 of an uninterrupted journey. They leave two rations here and return to camp 2 (not back to base). They refill with 10 of the 14 rations stored here and walk to camp 3. They leave six rations and return to camp 2. They take the remaining four rations from camp 2, walk to camp 3 and refill with the eight rations stored there. With full packs, they can now complete their journey.

This solution takes twice as many supplies and dramatically more time than the non-storable solution. Which is better depends on resource management (time/supplies vs people) and whether the five-days of rations limitation is due to perishability or weight ... if one were to care about practical issues in a puzzle.

$\endgroup$
  • 2
    $\begingroup$ I suppose I forgot to specify that it was disallowed (which it is). $\endgroup$ – Joe Z. May 26 '14 at 12:42
2
$\begingroup$

The 2 travelers need 16DoS (Days of Supplies). They can carry 10DoS. They need 6 more DoS. 2 people are needed to carry their DoS. We want the minimal amount of people, so let us just say that the 2 people use 3 DoS from the 2 other people, which means that the 3 DoS that they are using finishes in 3 days. They 2 other people need 12 more for the trip for 3 days and back, but they only have room for 4 DoS. They need other people to carry the 8 DoS. The number went from 6-->8 so this is a futile attempt of logic.

$\endgroup$
  • 1
    $\begingroup$ This answer is kind of unclear. Can you explain how these five explorers would walk each day? $\endgroup$ – Joe Z. May 18 '14 at 23:36
  • $\begingroup$ ok............. $\endgroup$ – awesomepi May 18 '14 at 23:46
  • $\begingroup$ I've added latex rending to this post, which will be enabled when they enable LaTeX here. $\endgroup$ – Aza May 19 '14 at 1:25
  • $\begingroup$ @Emrakul - awesomepi removed the edit. Now that we have MathJax, want to redo it? $\endgroup$ – Bobson May 30 '14 at 15:23
  • $\begingroup$ @Bobson I'm not sure it needs it any more, actually! If you can think of a good way to improve it, though, feel free to edit. $\endgroup$ – Aza May 30 '14 at 15:28
1
$\begingroup$

Assuming you have to feed the travelers on day 8: Solution 1: 8 leave and go to camp 1. Two refill the packs of the other six and return. Six go to camp 2. Four refill the packs of the others and return. Four go to camp 3. Two refill the packs of the two that will complete the trip and return.

Solution 2: Seven leave and go to camp 1. Two refill the packs of the other five, hide one ration, and return. Five go to camp 2. Two refill the packs of the other three, hide one ration, and return. Three go to camp 3. One refills the packs of the other two, who will complete the journey. He returns, using the hidden rations.

I believe the first solution is the desired one. It is tight: there is no food to spare. The second has a spare ration. The accepted answer has more slack. Usually setters try to avoid this and pick the parameters of the problem this way.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.