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
Answer
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.
No comments:
Post a Comment