Coconut and Monkey Puzzle

Date: 12/18/97 at 09:51:50
From: Betty Koestler
Subject: Coconut, monkey puzzle

Dear Dr Math:  

Please help me solve this puzzle.  

"Five men were stranded on an island. They went around picking up 
coconuts for years. One day, they saw a ship coming. They had a radio 
so they sent a message to come and pick them up. The ship said "yes, 
tomorrow morning!"  

The five men went to sleep but the first man woke up and thought "I 
don't trust my buddies," so he took 1/5 of the pile of coconuts.  
Then a monkey came down and took 1 coconut.  

The second man woke up and didn't trust his buddies either, so he took 
1/5 of the remaining pile of coconuts.  The monkey came down again and 
took 1 coconut.  

During the rest of the night, the third, fourth, and fifth men did the 
same and the monkey took 1 coconut after each man. 

In the morning, the five men tried to divide the remaining pile of
coconuts into five equal portions but had one left over, which they 
gave to the monkey.  How many coconuts were in the original pile?

My name is Leesa Marie and I am in the 4th grade at Washington School,
Greenville Mississippi.   Thank you for your help.

Date: 12/18/97 at 12:00:12
From: Doctor Rob
Subject: Re: Coconut, monkey puzzle

This problem, or variants of it, have been around for a long time.  
This is how you solve it.

Let a be the number of coconuts to start with. After the first man and 
the monkey took their coconuts, the number left was b = (4/5)*a - 1.
After the second man and the monkey took their coconuts, the number 
left was c = (4/5)*b - 1. The third man left d = (4/5)*c - 1 coconuts.  
The fourth man left e = (4/5)*d - 1 coconuts.  The fifth man left
f = (4/5)*e - 1 coconuts.  At the end, f = 5*g + 1, where g is the 
number of coconuts each man got in the morning.

Using the last equation, substitute in the previous one to get

           5*g + 1 = (4/5)*e - 1,
         5*(5*g+2) = 4*e,
         25*g + 10 = 4*e.

Now substitute that in the equation relating d and e:

         25*g + 10 = 4*[(4/5)*d - 1],
       5*(25*g+14) = 16*d,
        125*g + 70 = 16*d.

Now substitute that in the equation relating c and d:

        125*g + 70 = 16*[(4/5)*c - 1],
      5*(125*g+86) = 64*c,
       625*g + 430 = 64*c.

Now substitute that in the equation relating b and c:

       625*g + 430 = 64*[(4/5)*b - 1],
     5*(625*g+494) = 256*b,
     3125*g + 2470 = 256*b.

Now substitute that in the equation relating a and b:

     3125*g + 2470 = 256*[(4/5)*a - 1],
   5*(3125*g+2726) = 1024*a,
   15625*g + 13630 = 1024*a,
  1024*a - 15625*g = 13630.

Any positive whole numbers a and g which are a solution of this 
equation will give you a solution to your original problem.  The 
problem has been reduced to finding the value of a.

Notice that since 5 divides 15625 and 13630, but not 1024, that 5 must
divide a, so a = 5*h.  Then

   1024*5*h - 15625*g = 13630,

or, dividing by 5 througout,
  
      1024*h - 3125*g = 2726.

Similarly, since 2 divides 1024 and 2726, but not 3125, 2 must divide 
g, so g = 2*i, and

    1024*h - 3125*2*i = 2726,
       512*h - 3125*i = 1363.

Now we can tell that i must be odd, so i = 2*j + 1, and

 512*h - 3125*(2*j+1) = 1363,
     512*h - 3125*2*j = 1363 + 3125 = 4488,
       256*h - 3125*j = 2244.

Next, since 4 divides 256 and 2244, but 2 doesn't divide 3125, 4 must
divide j, so j = 4*k, and

     256*h - 3125*4*k = 2244,
        64*h - 3125*k = 561.

Similarly, k must be odd, so k = 2*m + 1, and

   32*h - 3125*m = 1843.

Similarly, m must be odd, so m = 2*n + 1, and

   16*h - 3125*n = 2484.

Now n must be divisible by 4, so n = 4*p, and

    4*h - 3125*p = 621.

Again, p must be odd, so p = 2*q + 1, and

    2*h - 3125*q = 1873.

Further, q must be odd, so q = 2*r+1, and

      h - 3125*r = 2499.

One solution to this is r = 0, h = 2499.  There are other, larger 
ones, such as r = 1, h = 5624, and r = 100, h = 314999, but we will 
stick with the smallest one.  The general solution is h = 2499 + 3125*
r, r any nonnegative whole number.

Backtracking, we get q = 1, p = 3, n = 12, m = 25, k = 51, j = 204,
i = 409, h = 2499, g = 818, f = 4091, e = 5115, d = 6395, c = 7995,
b = 9995, and a = 12495.  Sure enough,

   1024*12495 - 15625*818 = 13630.

Does this work?  Let's check.

Starting with 12495:
The first man took 2499 coconuts, and the monkey took 1.
  This left 12495 - 2500 = 9995 coconuts.
The second man took 1999 coconuts, and the monkey took 1.
  This left 9995 - 2000 = 7995 coconuts.
The third man took 1599 coconuts, and the monkey took 1.
  This left 7995 - 1600 = 6395 coconuts.
The fourth man took 1279 coconuts and the monkey took 1.
  This left 6395 - 1280 = 5115 coconuts.
The fifth man took 1023 coconuts and the monkey took 1
  This left 5115 - 1024 = 4091 coconuts.
In the morning, each man got 818 coconuts and the monkey 1 more.

It checks!  Hooray!

If we backtrack using h = 2499 + 3125*r, we will find that the general
answer is a = 12495 + 15625*r coconuts, for any nonnegative whole 
number r.

The men must have done a whole lot of counting in the middle of the 
night!

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