9
$\begingroup$

Background Story

A nomad is injured in the desert. And he can't move, but fortunately an oasis is nearby, and he can stay there for enough time until rescue arrives. But the water is a magical water, that it can't be stored. So it should be drunk immediately or it'll disappear. In other words, one cannot bring the water outside the oasis.

The other nomad friends, know the exact position of the injured nomad, which is $n$ days away from the base. The nomads are going to send delegations to save him, but the problem is that each nomad can only bring food supply for one nomad for $3$ days. The base has arbitrarily large number of nomads inside, so they decided to send a group of nomads to rescue the injured nomad, that is, to go to the place of injured nomad, and then go back to the base. All nomads must survive. But they have weird cultural rules, which is each time a nomad leaves the base, they have to kill a sheep as redemption.

Note that the injured nomad also need to eat while going back to the base.

Question

What is the number of sheep need to be slaughtered in order to save the injured nomad in case n=2? n=3? arbitrary n?

Furthermore, what is the minimum number of days required to save the nomad?

Example

For example, if n=1, the nomad group can just send one nomad. It'll consume 1 day of supply, then arrives at the injured nomad place with 2 days of supply left, then each of them consume 1 day of supply while going back to the base, leaving no supply left when they arrived at the base. Since only one nomad leaves the base, only one sheep is killed. So 1 sheep will be slaughtered, and the rescue time is 2 days.

Notes

|improve this question
$\endgroup$
  • 1
    $\begingroup$ Could you make an example with all elements of puzzle used? (I still do not get oasis thing). $\endgroup$ – klm123 Jul 3 '14 at 6:22
  • 1
    $\begingroup$ Or this is exactly the Travellers across a desert puzzle where 8->n, 5->3? $\endgroup$ – klm123 Jul 3 '14 at 6:24
  • $\begingroup$ Can other nomads drink from the oasis while they wait for other people to bring them back? $\endgroup$ – Joe Z. Jul 3 '14 at 6:42
  • $\begingroup$ Can they leave usual water in the desert? $\endgroup$ – klm123 Jul 3 '14 at 7:08
  • 1
    $\begingroup$ Nomad must be able to go without eating at least one day or else injured nomad would die. Are we assuming that drinking from the oasis is just as good as eating? Also, if you have nomads more than 3 days away from base, there is no way they can all make it back, even at 3 day of food rations. $\endgroup$ – Neil Jul 3 '14 at 13:57
6
$\begingroup$

Using Joe Z.'s method for $n=2$, I can think of a strategy for $n=3$ in $6$ days killing $13$ sheep. Pretty sure this is the minimum amount of days because it's $2n$. Not sure if it is the minimum amount of sheep.

I won't do a day by day guide like Joe but my explanation hopefully is clear.

First start off with $2$ nomad's. After $1$ day one nomad gives a day supply to the other and heads back. So, the one returning has just enough to get back and the other has a full three-day supply.

From his point of view it now is only an $n=2$ problem because he is now at distance $1$ with full supply.

So use the $n=2$ strategy here. You can do this by sending an extra nomad for each nomad that needs to be at $1$ day travel with full supplies.

The $n=2$ strategy eventually also returns all these nomad's at this point with no food left so for each of them they need an extra nomad to supply them.

So to sum it up: start sending $2$ nomads every day for $4$ days. half of them return. the other half does the $n=2$ strategy. One day before they are finished send $5$ nomads away so they meet up with the other five when they are finished with their $n=2$ strategy. The now $10$ nomads have exactly enough to return. counting the $4$ that returned in the beginning and not counting the stranded nomad, that's $13$ sheep that were killed.

ADDITION AND CONCLUSION:

you can generalize strategy this by doing same thing for other $n$. You will have then: sheep killed for $n$ is three times the [number of sheep killed for strategy $n-1$] plus one. And days to take is always $2n$.

Given this, this strategy is equally good as Joe's with going to $n=1$ one to $n=2$. because $3*1+1 = 4$ sheep.

And $n=2$ worked out to be:

D0: 2 nomads leave (N1 and N2)

D1: N1 gives 1 supply to N2 and heads back

D2: N2 arrives at N0 and gives him 1 supply and start heading back. N3 and N4 leave.

D3 N3 and N4 meat up with N0 and N1 and they give them each a supply.

D4: they all arrive back with their supply used up.

So wrapping it up. If $F(n)$ is the amount of sheep necessary or a nomad stranded at $n$ days distance.

$$F(1) = 1$$

$$F(n) = 3*F(n-1) + 1$$

And days it takes is always $2n$.

I'm not that good in math but I know there is a simple way to convert this recursive formula to a direct one.

|improve this answer
$\endgroup$
  • $\begingroup$ Here's a tip on the closed form: $F(2)=3+1$, $F(3)=3*3+4$, $F(4)=3*3*3+13$; I'm seeing $3^{n-1}$ and A003462. $\endgroup$ – user20 Jul 3 '14 at 15:25
  • $\begingroup$ Great! This is the answer that I have in mind. I like this problem since the impossible is actually possible. It seems at first impossible to get everybody back while each nomad can only bring 3 days worth of supply. I had the same recurrence relation. Accepted! $\endgroup$ – justhalf Jul 3 '14 at 15:58
  • 2
    $\begingroup$ By the way the closed form is $F(n) = \frac{3^n-1}{2}$ $\endgroup$ – justhalf Jul 3 '14 at 16:02
5
$\begingroup$

While I don't have a solution to the whole problem just yet, here's a solution for $n = 2$ in 4 days:

T+0 days: a single nomad (1) leaves and travels 1 day forward.

T+1 day: a single nomad (2) leaves, and both nomads travel one day forward. Nomad 1 reaches the oasis, with one day of supplies left, which he shares with the stranded nomad (nomad 0).

T+2 days: a single nomad (3) leaves, and nomads 0 and 1 go back for 1/2 day, running out of supplies. Nomad 2 meets them at 1.5 days out, with 1.5 days of supplies left, which he shares with the two other nomads.

T+2.5 days: The group of three nomads go back for 1/2 day, meeting nomad 3 at 1 day out, with 2.0 days of supplies left, which he shares with the three other nomads.

T+3.0 days: a single nomad (4) leaves, and the group of four nomads go back for 1/2 day, meeting nomad 4 at 0.5 day out, with 2.5 days of supplies left, which he shares with the four other nomads.

T+3.5 days: The group of five nomads head back to base in 1/2 day with just enough supplies to make it.

This solution is rather elegant, because it only requires four nomads to set out at T + 0, 1, 2, and 3 days (and thus four sheep are slaughtered), and all the resources are used up exactly when they're needed (every time the nomads run out of supplies, a nomad is there to provide just enough for yet another nomad to meet them in the middle). I'd be surprised if a better solution existed.

|improve this answer
$\endgroup$
  • $\begingroup$ A nice one, for $n=2$ this is clearly the optimal solution since 4 days is obviously the minimum number of days, and all supplies are used up. It's a bit confusing to follow the half-day, though. Now, how about a general solution? Note: In "nomads 0 and 1 go back" perhaps you meant "nomads 1 and 2 go back". $\endgroup$ – justhalf Jul 3 '14 at 8:29
  • $\begingroup$ Oh, I just remember that nomad 0 refers to the injured nomad. That's correct then. Also while this is elegant, the general solution that I have is more elegant IMHO. =) $\endgroup$ – justhalf Jul 3 '14 at 8:39
  • $\begingroup$ @justhalf, so there is a known solution? Good to know. Do you have a prove that it is optimal (minimum sheep to kill) as well? $\endgroup$ – klm123 Jul 3 '14 at 8:53
  • $\begingroup$ I don't have very rigorous proof, but the line of reasoning is similar to yours, that they return in the minimum number of days and all resources used are necessary and that there is no leftover. $\endgroup$ – justhalf Jul 3 '14 at 8:59
  • $\begingroup$ @klm123: Oops, I mean Joe's line of reasoning. Didn't realize you're not the answerer. haha $\endgroup$ – justhalf Jul 3 '14 at 9:18
3
$\begingroup$

I have this answer for $n$, but in the end I lack the mathematical skills to come to a single formula.

The general principle will be like this: You send a big group into the dessert. After each day, half of the nomads in the (remaining) group will give food to the other half and travel back one day. The nomads that are fully equiped travel one day further. This means that when the oasis is $n$ days away, the original group needs to be $2^{n-1}$ to make sure that one nomad arrives in the oasis with $2$ food left needed to take himself and the injured nomad to travel back one day.

Now all we need to do is send groups to resupply the parties that were starting their return. This can be seen as more of the same rescue operations. There are $2$ nomads at $n-1$ that need to be rescued, and furthermore, $1$ at $n-2$, 2 at $n-3$, $4$ at $n-4$ and so on. This can be written as $2^x$ people need to be rescued at $n-2-x$ for every $x$ from $0$ to $n-3$. It is $n-3$ since the last people that need rescuing will be at location $1$.

This means that if $f(n)$ is the total amount of people that need to leave the base to rescue one person at $n$ then:

$$f(n) = 2^{n-1} + 2\cdot f(n-1) + \sum_0^{n-3} 2^x \cdot f(n-2-x)$$

I am not able to solve the above formula, but I hope the general idea is clear.

And the amount of time is $2n$, which can easily be seen since the ultimate rescuer travels there in one go and returns in one go as well.

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Seems harder to solve, but since I know the correct solution, I can use that to do induction using your recurrence relation. It's correct. Congrats for finding an alternative solution (although more complex)! $\endgroup$ – justhalf Jul 3 '14 at 16:21

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.