Food for thought...
A crazy (suspected Brit?) explorer wishes to cross a desert on foot. It takes six days to cross the desert. One man can carry enough food for only 4 days. Under this scenario, using trial and error, you can find the fewest number of men required so that the explorer crosses the desert and the coolie(s) return(s) alive. What is this minimum number? (0.1 point - sorry, this is easy!)
The real question (1.0 point) is to find an elegant logic to generalize this problem. That is, if it takes N days for an explorer to cross the desert and each man can carry enough food for k days, what algorithm should be employed to attain the objective?
The real question (1.0 point) is to find an elegant logic to generalize this problem. That is, if it takes N days for an explorer to cross the desert and each man can carry enough food for k days, what algorithm should be employed to attain the objective?
posted by littlecow at 1/24/2006 05:38:00 PM
19 Comments:
u didn't specify if the coolies returning should be non-zero. if zero is allowed, 2 guys for the initial question. one guy is left in the desert after 2 days, and the explorer takes his 2 days worth of food and the finishes the journey.
if u want at least one coolie to return, then 4 guys total including the explorer. at t=1 day, 1 guy is left behind and the food level = 4*(4-1) = 12. need food for for 1 guy for 5 more days and food for another guy for 1 day (to go back). at t=2.33days, one more guy left behind and food level = 7. need food for 1 guy for 4 days and another guy for 2 days. there is food for 7 days, requirement is only 6, thus 1 guy can mke it back and the explorer can make it to the other side, 2 guys sacrificed total.
for the general solution, my approach was to minimse the number of guys carrying the load such that each guy always carries the maximum possible load, i.e. k days worth, so let's say there are m men, including the explorer. total food = k*m. so they keep travelling for x days till the food drops to k*(m-1), which is also equal to m*(k-x) i.e. food consumed. equating k(m-1) = m(k-x), we find that x = k/m. Now eliminate one guy, and the problem is redefined as N-x days left , i.e. N- k/m days left, k is still the carrying capacity and m-1 men left.
so N,k,m becomes
N-k/m, k, m-1 becomes
N-k/m-k/(m-1),k, m-2 etc. etc.
till N - k/m - k/(m-1) - k/(m-2) ... k/(m-i) = k days and then the explorer has k days worth of food and finishes. the remaining dudes (m-i-1) die. Here, I have assumed that zero guys need to return.
For the general case where at least one guy needs to return, it's more involved, I think.
ok, i'll wait till u guys tell me i'm thoroughly confused.
@lens: this is a peaceloving blog. nobody dies. the explorers are all lovely and all the coolies, no matter how lowly, return alive.
damn, after all work i put into that solution. ok saami, very noble of u, shall rework.
ok answer to first one is: 3 guys total.
all start with 4 days worth of food.
after day 1, coolie1 goes back, thus he consumes 2 days of food and gives the remaining 2 days to the other two.
so the other two start day 2 with 4 days worth of food. at the end of day 2, coolie2 goes back and gives the remaining 1 day worth of food to the explorer who starts day 3 with 4 days worth of food enough to get him to the other side.
I think 2 are enough because there is no advantage in taking the second guy there at all.
I mean 2 guys start with 8 days worth of food.
End of day 1: 6 days food remains.
Day 1: slave returns with 1 day food. Food remaining with explorer = 5 days worth. and he travels to the other end in those 5 days.
No sorry... Lenscrafter is right off course....
It takes 3 people.
lenscrafter is right. now that we have the minor issue out of the way, go for the main problem.
Suppose m+1 guys start... with m coolies that is.. I'll make some assumptions to begin with. If things don't work out, let us try to relax some.
Assmption1: Coolies turn back at equal intervals after t=0. So the m guys turn back at times t, 2t,..mt, and there have to consumer 2t(1+2+..m) units of food=tm(m+1) units.
Our British hero will totally eat N of course.
Assumption 2: Fractional m's allowed... (Screw the other problems.)
Any solution in which the hero has less than k days left to go and has the company of a coolie has to be suboptimal.
So we know the last coolie returns at time mt=N-k (which is related to assumption 2 somehow - go figure, i lost my train of thought!)
Now, we know neither m nor t. But the food equality can be used.
For the N days demand== supply, i.e.
tm(m+1)+N==k(m+1)
Combining this with mt=N-k, you should get
m+1=N/(2k-N) as the answer, i think.
For the N=6, k = 4 days, m+1=3, which seems to be Lenscrafter's soln...
The non-integrality assumption can be relaxed by creating a non-linear mixed integer program with demand and supply constraints as above.
Intuitively, I feel that if there is 1 solution to the problem, there should be another in which coolies return at equal intervals that gives the same m.
But if you relax both at the same time, the answer *may* be more complex.
My approach starts off differently compared to Sisyphus', but I seem to converge to his solution. Further, I think I also proved equal time intervals. Will wait for the experts to shoot this down.
Reasoning:
The aim is to make sure the explorer has a food level of k days till N-k days have passed.
No food should be wasted.
If the explorer/coolies can carry extra food, they should be refill immediately.
The above 3 lead to the conclusion that a coolie is useless as soon as his food load reaches exactly the same amount as the sum of the food needed for him to go back + the food needed to refill everyone else other than him to a food level of k.
There are a total of 'm' men. Let's say after 't0' days, a coolie has just enough to refill the other m-1 men to a food level of k and to go back with the remaining food. If he continues any longer, he is just wasting food by carrying food that could be carried by someone else. On the other hand, he has to continue till that point, since he cannot offload all the food to the others without wasting some before 't0' days.
This gives the equation for the food consumption of that coolie, with (m-1) men remaining: k-2*t0 = (m-1)*t0
which implies that t0 = k/(m+1)
Now, assume that the next coolie continues till a point t1 defined by an argument similar to above, i.e. he continues only till he has exactly enough food to go back + refill all the others to k. No more, no less for same reasons as above.
The second coolie needs (t0 + 2*t1) amount of food from the point t=t0. Remember, he has already refilled to k at t=t0.
this give the equation of food consumption for the second coolie, with (m-2) men remaining: k-t0-2*t1= (m-2)*t1, which gives: t1 = (k-t0)/m = k/(m+1) = t0. So basically, the fraction k/(m+1) is the time interval at which each coolie starts dropping off. The reduction in the amount of men compensates exactly with the extra distance travelled by the man dropping off. So, if the men have reduced to m-3, the guy going back has to travel 3 times the distance of the previous two guys etc. etc.
If this calculation goes on, you can see that t0=t1=t2= ... tm = k/(m+1).
At t=N-k, the last coolie starts back for a journey of N-k days. Thus, N-k = m*tm = m*k/(m+1), which gives m = N/(2k-N).
Of course, my m = Sisyphus' (m+1), so the two solutions seem to agree.
@grenade: I don't make any assumptions about "organizing" coolie returns. I only use the stated requirement that every coolie who leaves must return. And within that framework, I looked for the simplest possible answer using supply/demand constraints. It might be wrong. Hey, the main part of my post is actually very short (assumptions rock!)
@lenscrafter: may be grenade's qn was at u. do u want to answer that? it seems like u have thought in more detail abt the Coolie transportation issue than I have...
@grenade,sisyphus: my solution does not assume coolie re-returns. a coolie goes till the point where he is most useful without wasting food, and returns immediately when his services become redundant. he does not make another trip to refill etc. what i meant by refill is just topping up the capacity of everyone with a coolie's excess load when he returns. apologiess for the inelegant way to describe some of these solutions.
saami, enna da no response ??
bro, i was a bit busy here (not entirely with work i might add)... and could not check the comments out in detail. worry not - i will get back to it...
@lenscrafter, sisyphus: all good trains of thought. but i have one question for you (other than grenade's question, which still remains valid). The first coolie returns on day 1, the second on day 2 and so on. The last coolie returns on day N-k.
Therefore, m=N-k (which for the test case gives 2=6-4!). But then, something is quite wrong as combining this with your solution eliminates m from the equation altogether connecting two independent variables!
Whats wrong?
@littlecow: the spacing is not always 1 day. it depends on m as t = k/(m+1). so if k=4 and there are a total of 5 guys, t = 0.8 days. i'm not assuming coolies being refilled on the way back, and thus does not assume coolie re-returns as I explained above.
@lenscrafter: i am not sure about your and sisyphu's answers then. i quote verbatim from your solutions:
sisyphus: "Coolies turn back at equal intervals after t=0. So the m guys turn back at times t, 2t,..mt,"
lenscrafter: "At t=N-k, the last coolie starts back for a journey of N-k days"
From the above, it appears that the coolies start back at the end of integral days.
I am still unconvinced by the answers, boys!
This comment has been removed by a blog administrator.
Balaks, that is correct, the last coolie does start back at the end of an integral number of days. It is the time slices that are non-integral days. Total time = N-k, time slices = non-integral = k/(m+1).
According to the above, it is not necessarily an integral number of days for the turn back time of any coolie except the last one.
Post a Comment
<< Home