Monkeys in the Jungle

Date: 11/18/96 at 17:57:38
From: DR STEVEN R BERKMAN MD
Subject: Monkeys in the jungle...

A group of monkeys are hanging from some trees and see a pile of 3000 
bananas (monkeys have a way of knowing exactly how many bananas are 
in a pile).  They want to bring the bananas to their friends 1000 
miles away on the other side of the jungle.  So, they swing through 
the jungle carrying as many bananas as they can to the other side.  
The monkeys are indecisive, so they don't necessarily make one trip.  
Altogether, they can carry up to 1000 bananas at any given time, but 
every mile the group shares one banana.  Since the monkeys are good 
friends, they always stick together.  What is the MAXIMUM number of 
bananas the group of monkeys will be able to bring to their friends 
on  the other side of the jungle?  How do they do it?

Date: 11/20/96 at 17:11:17
From: Doctor Lynn
Subject: Re: Monkeys in the jungle...


I ran this through a spreadsheet and eventually came up with this 
answer: (starting with 1000 bananas each time)

They go 250 miles and drop 500 bananas and come back.
They go 250 miles, pick up 250 bananas, go another 250 miles, drop 250 
bananas and come back.
They go 250 miles, pick up the 250 bananas, go 250 miles, pick up the 
other 250 bananas and reach their friends with 500 bananas.

Not a particularly nice way of solving the problem and it may not be 
the  MAXIMUM number, but I haven't been able to find a better one.  
Perhaps one of the other Doctors will be more help.

-Doctor Lynn,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   

Date: 11/21/96 at 03:14:34
From: DR STEVEN R BERKMAN MD
Subject: Re: Monkeys in the jungle...

Dr. Lynn:
  Thank you for your reply.
  But what if they go 333.3 miles and drop 666.7....
  Go back and get another 1000...go 333.3 and drop another 666.7..
  Go back and get the last 1000...go 333.3 and drop another 666.7.

  Now they have 2000 at the first point...
  Take 1000 and go another 333.3 mi and drop 666.7...
  Go back...get the last 1000...go the 333.3 and drop 666.7...
  Now they have 1333.333 two thirds of the way there...
  They pick up 1000...go the last 333.3  and drop 666.66666666
  Go back....get the last 333.33 and then share the 666.666 with their 
friends?

  In one of your archives is the problem using a camel...and they 
came up with 533.33 bananas...

WE'RE SO CONFUSED!

Any suggestions?
Again, thanks for your help.
DOCT99D
Steven Berkman, M.D.

Date: 11/27/96 at 16:13:10
From: Doctor Ceeks
Subject: Re: Monkeys in the jungle...

Hi,

First of all, I'll assume that the bananas are actually eaten
continuously, and not after each mile.  After all, if the bananas
are actually eaten only after each whole mile, then one could get all
3000 bananas any distance by carrying 1000 bananas half a mile at
a time.

Indeed, it may be conceptually better to think of this problem as
monkeys carrying sacks of sand which leak at the rate of 1 pound
per mile.  This model more accurately describes the problem based
on the kinds of statements you have made (such as that the monkeys
can go back without using bananas and that there can be fractional
amounts of bananas).

So, I will phrase my answer in terms of sand, but you can replace
sand with bananas if you want.

(The final answer will be that 833 1/3 pounds of sand (bananas)
can be brought to the destination.)

Note that as long as there are more than 2000 pounds of sand, at
least three trips are required to move all the sand some distance no
matter how the sand is distributed along the path.

We can therefore succeed in getting 2000 pounds of sand one third
of the way to the destination by taking three trips one third of
the way and back.  This is what you do to start off your answer below.

Now, as long as there are more than 1000 pounds of sand, at least
two trips are required to move all the sand some distance no matter
how the sand is distributed along the path.

We can therefore succeeed in getting 1000 pounds of sand one third 
plus one half of the way to the destination by making two trips of 500 
miles each.

At this stage, there are 1000/6 miles to go, and this done, we reach
the destination with 1000-1000/6=833 1/3 pounds of sand.

Now we ask, why is this the best possible?

Here, I will give a heuristic argument.  I hope this argument will be 
convincing enough but I do want to point out that it is not a 
completely rigorous mathematical argument as it stands. However, it 
can be made rigorous with some extra effort (which I'm sorry for not 
wanting to do!).

Imagine a very short segment of the path...say a foot long.  For this
one foot segment, we ask, how many trips are taken across this segment 
by sand bearing monkeys?  The amount of sand lost to the earth on this 
segment is a multiple of the number of such trips.

Now, we can imagine cutting the whole path into these 1 foot segments 
and placing a number over each segment indicating how many sand 
bearing trips are taken over that segment.

For instance, a silly thing to do would be to carry 1000 pounds all 
the way in three separate trips resulting in no sand at the 
destination. Each segment would be assigned the number 3 because each 
1 foot segment saw 3 sand bearing monkey trips crossing it.

In the solution given above, there would be 3's over segments in the 
first third of the path, 2's over the next 500 miles, and 1's over the 
remaining sixth.

Now, how ever the monkeys originally got the sand over to produce
the assignment of numbers to the segments that we see, we can
always make the monkeys move the sand over foot by foot (segment by
segment) taking as many trips as indicated by the numbers to arrive
at a solution which results in the same amount of sand at the 
destination, but with the property that the sand is moved one segment 
at a time.

For instance, in the silly strategy, we took three trips of 1000 miles
each.  But we could also move 1000 pounds a foot, go back, move 1000
pounds a foot, go back, move 1000 pounds a foot.  Then, divide what
sand is left into thirds, and move each of the three piles of sand
another foot, according to the prescription described in the last 
paragraph.  The amount of sand arriving at the destination will be the 
same as the silly strategy, but the monkeys will behave very 
differently along the way.

The key point of doing this is that we can now see that the furthest
we can encounter a segment assigned a 2 to the starting point is
1000/3 miles into the path.  This is because we want to minimize
the losses for as long as possible, and this can be done only by
assigning 3's as far as possible.  Doing so, reduces the sand to
2000 pounds by the 1000/3 mile mark.  Any other strategy will result
in a loss of a thousand pounds at an earlier stage.

Now observe that the best strategy must do this, because the best
strategy will observe 2000 pounds of sand occuring closest to the
destination.  (If there were a strategy which observed 2000 pounds
occuring earlier, then there would be less than 2000 pounds at the
1000/3 mile mark and so the strategy of getting 2000 pounds to the
1000/3 mile mark must do at least as good.)

By similar reasoning, the furthest we can encounter a segment assigned
a 1 is 500 miles further or at the 5/6 of 1000 mile mark.

(And, of course, 1 is the minimum possible value a segment can be 
assigned unless the monkeys lose all the sand before getting to the 
destination!)

It is true that there is the objection that using segments 1 foot long 
forbids strategies which have monkeys going distances that are not 
multiples of 1 foot.  However, we can take the length of each segment 
to be arbitrarily small.  If you know calculus, you can check that "in 
the limit", that is as the length of these segments tends to 0, you 
will achieve the same answer given above.

-Doctor Ceeks,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   

Date: 11/27/96 at 23:46:22
From: DR STEVEN R BERKMAN MD
Subject: Re: Monkeys in the jungle...

Doctor Ceeks:
  Thank you for your reply to my query.
  However, the monkeys eat one banana for every mile they travel... 
whether it be forward, toward their eventual goal, or backwards, to 
pick up more bananas.
  The consensus seems to be that 533 1/3 is the correct number.

Steven Berkman, M.D.
DOCT99D@prodigy.com

Date: 12/04/96 at 14:16:04
From: Doctor Ceeks
Subject: Re: Monkeys in the jungle...

Hi,

According to your response earlier where your wrote

      But what if they go 333.3 miles and drop 666.7....
      Go back and get another 1000...go 333.3 and drop another 666.7..
..
      Go back and get the last 1000...go 333.3 and drop another 666.7.

      Now they have 2000 at the first point...


it implies that the monkeys go backward without having to carry
any bananas.  If this is the case, then my answer is correct.

If in fact the monkeys must eat bananas going backward too, then
if they go 333.3 miles, they ate 333.3 bananas and they could only 
drop off 333.3 bananas since they would need 333.3 bananas in order to 
go back to the starting point.

On the other hand, if you are saying that the monkeys would eat
bananas going back IF they were carrying bananas, then that's ok,
my solution accounts for this too.

Let me say again my solution:

Carry 1000 bananas 333 1/3 miles and drop off 666 2/3 bananas.
Go back and get another 1000, go 333 1/3 and drop off another 666 2/3.
Go back and get another 1000, go 333 1/3 and drop off another 666 2/3.
Now they have 2000 at the first point (which is 333 1/3 miles from
the starting point).

This is exactly the same as the way you start in one of your 
responses.

Now, carry 1000 bananas another 500 miles further to the 833 1/3 mile
mark and drop off 500 bananas.  Go back and get the remaining 1000 
bananas and travel 500 miles to the 833 1/3 mile mark and drop off 500 
bananas.

Now there are 1000 bananas at the 833 and 1/3 mile mark.

Carry these 1000 bananas another 166 2/3 miles to the destination
and drop off 833 and 1/3 bananas.

(The answer in the archives is not an answer.  It is just a suggestion
at what the answer may be.)


-Doctor Ceeks,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   

Date: 12/04/96 at 14:54:24
From: Doctor Ceeks
Subject: Re: Monkeys in the jungle...

Hi,

Above, you actually found a solution which deliver 666 2/3 bananas, so 
I'm confused why you wrote that you think the consensus is that 
533 1/3 is correct?

By the way, if the monkeys require a banana per mile in order to move
anywhere, forward or back, then the answer is, indeed, 533 1/3.

The proof can be modelled on similar lines as in the message I sent
which gives a proof (assuming travel distances which are multiples
of a foot) that 833 1/3 is the maximum value for monkeys which can
travel back without carrying any bananas (as you have assumed
in the method below).

To overcome the "1 foot" problem, one can define a function F
from points on the path to the integers by letting F(x) be
the number of times monkeys cross x.  Here, the condition that
the monkeys be banana bearing is unnecessary because it is now
required at the outset that monkeys must always carry bananas!

But, also, it should be assumed that the monkeys only make a finite
number of changes of direction, which is quite reasonable to assume.

Then one can mark the points of change of direction and make the 
monkeys walk a new route (as in the other solution) but with the same 
effect in terms of bananas delivered.

One then argues that the furthest along 2000 bananas can get is 200 
miles into the path.  Then one argues that the furthest 1000 bananas 
can get is 200+333 1/3 = 533 1/3 miles along the path.  Then, they 
just carry the 1000 bananas to the destination and arrive with 533 1/3 
bananas.

Specifically, it can go like this:

-Carry 1000 bananas 200 miles, drop off 600 bananas, return consuming
 all remaining 200 bananas to get back to the start.
-Repeat the above again.
-Now carry 1000 bananas 200 miles so at the 200 mile mark, there are
 600+600+800 = 2000 bananas.

-Now carry 1000 bananas 333 1/3 miles, drop off 333 1/3 bananas, go
 back 333 1/3 miles, pick up the 1000 bananas, go 333 1/3 miles so
 at the 533 1/3 mile mark, there are 333 1/3 + 666 2/3 = 1000 bananas.

Now carry the 1000 bananas to the destination and arrive with
533 1/3 bananas.

-Doctor Ceeks,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/